Vertex coloring

List chromatic number and maximum degree of bipartite graphs ★★

Author(s): Alon

Conjecture   There is a constant such that the list chromatic number of any bipartite graph of maximum degree is at most .

Keywords:

Colouring the square of a planar graph ★★

Author(s): Wegner

Conjecture   Let be a planar graph of maximum degree . The chromatic number of its square is
\item at most if , \item at most if , \item at most if .

Keywords:

Weighted colouring of hexagonal graphs. ★★

Author(s): McDiarmid; Reed

Conjecture   There is an absolute constant such that for every hexagonal graph and vertex weighting , Keywords:

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

Author(s): Zhu

Question   Are there graphs for which is arbitrarily large?

Choosability of Graph Powers ★★

Author(s): Noel

Question  (Noel, 2013)   Does there exist a function such that for every graph , Erdős–Faber–Lovász conjecture ★★★

Author(s): Erdos; Faber; Lovasz

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

Keywords: chromatic number

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

Author(s): Hoang; McDiarmid

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

Keywords: maximum clique; Partitioning

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

Author(s): Allagan

Question   Given , what is the smallest integer such that ?

Author(s): Kawarabayashi; Mohar

Conjecture   Every -minor-free graph is -list-colourable for some constant .

Keywords: Hadwiger conjecture; list colouring; minors

Cycles in Graphs of Large Chromatic Number ★★

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

Conjecture   If , then contains at least cycles of length .

Keywords: chromatic number; cycles 