Home » Subject » Graph Theory » Coloring

Vertex coloring


Graph Theory » Coloring » Vertex coloring

List chromatic number and maximum degree of bipartite graphs ★★

Author(s): Alon

Conjecture   There is a constant $ c $ such that the list chromatic number of any bipartite graph $ G $ of maximum degree $ \Delta $ is at most $ c \log \Delta $.

Keywords:

Posted by fhavet
updated March 12th, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

Colouring the square of a planar graph ★★

Author(s): Wegner

Conjecture   Let $ G $ be a planar graph of maximum degree $ \Delta $. The chromatic number of its square is
    \item at most $ 7 $ if $ \Delta =3 $, \item at most $ \Delta+5 $ if $ 4\leq\Delta\leq 7 $, \item at most $ \left\lfloor\frac32\,\Delta\right\rfloor+1 $ if $ \Delta\ge8 $.

Keywords:

Posted by fhavet
updated March 13th, 2013
add new comment | 1 attachment
Graph Theory » Coloring » Vertex coloring

Weighted colouring of hexagonal graphs. ★★

Author(s): McDiarmid; Reed

Conjecture   There is an absolute constant $ c $ such that for every hexagonal graph $ G $ and vertex weighting $ p:V(G)\rightarrow \mathbb{N} $, $$\chi(G,p) \leq \frac{9}{8}\omega(G,p) + c $$

Keywords:

Posted by fhavet
updated March 13th, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

Bounding the on-line choice number in terms of the choice number ★★

Author(s): Zhu

Question   Are there graphs for which $ \text{ch}^{\text{OL}}-\text{ch} $ is arbitrarily large?

Keywords: choosability; list coloring; on-line choosability

Posted by Jon Noel
updated April 11th, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

Choosability of Graph Powers ★★

Author(s): Noel

Question  (Noel, 2013)   Does there exist a function $ f(k)=o(k^2) $ such that for every graph $ G $, \[\text{ch}\left(G^2\right)\leq f\left(\chi\left(G^2\right)\right)?\]

Keywords: choosability; chromatic number; list coloring; square of a graph

Posted by Jon Noel
updated July 13th, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

Erdős–Faber–Lovász conjecture ★★★

Author(s): Erdos; Faber; Lovasz

Conjecture   If $ G $ is a simple graph which is the union of $ k $ pairwise edge-disjoint complete graphs, each of which has $ k $ vertices, then the chromatic number of $ G $ is $ k $.

Keywords: chromatic number

Posted by Jon Noel
updated August 22nd, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

2-colouring a graph without a monochromatic maximum clique ★★

Author(s): Hoang; McDiarmid

Conjecture   If $ G $ is a non-empty graph containing no induced odd cycle of length at least $ 5 $, then there is a $ 2 $-vertex colouring of $ G $ in which no maximum clique is monochromatic.

Keywords: maximum clique; Partitioning

Posted by Jon Noel
updated August 25th, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

List Colourings of Complete Multipartite Graphs with 2 Big Parts ★★

Author(s): Allagan

Question   Given $ a,b\geq2 $, what is the smallest integer $ t\geq0 $ such that $ \chi_\ell(K_{a,b}+K_t)= \chi(K_{a,b}+K_t) $?

Keywords: complete bipartite graph; complete multipartite graph; list coloring

Posted by Jon Noel
updated April 12th, 2014
add new comment
Graph Theory » Coloring » Vertex coloring

List Hadwiger Conjecture ★★

Author(s): Kawarabayashi; Mohar

Conjecture   Every $ K_t $-minor-free graph is $ c t $-list-colourable for some constant $ c\geq1 $.

Keywords: Hadwiger conjecture; list colouring; minors

Posted by David Wood
updated July 7th, 2014
add new comment
Graph Theory » Coloring » Vertex coloring

Cycles in Graphs of Large Chromatic Number ★★

Author(s): Brewster; McGuinness; Moore; Noel

Conjecture   If $ \chi(G)>k $, then $ G $ contains at least $ \frac{(k+1)(k-1)!}{2} $ cycles of length $ 0\bmod k $.

Keywords: chromatic number; cycles

Posted by Jon Noel
updated September 20th, 2015
add new comment

Note: Resolved problems from this section may be found in Solved problems.


Syndicate content