coloring

Crossing numbers and coloring ★★★

Author(s): Albertson

We let denote the crossing number of a graph .

Conjecture   Every graph with satisfies .

Keywords: coloring; complete graph; crossing number

Are vertex minor closed classes chi-bounded? ★★

Author(s): Geelen

Question   Is every proper vertex-minor closed class of graphs chi-bounded?

Keywords: chi-bounded; circle graph; coloring; vertex minor

Graphs with a forbidden induced tree are chi-bounded ★★★

Author(s): Gyarfas

Say that a family of graphs is -bounded if there exists a function so that every satisfies .

Conjecture   For every fixed tree , the family of graphs with no induced subgraph isomorphic to is -bounded.

Keywords: chi-bounded; coloring; excluded subgraph; tree

Domination in plane triangulations ★★

Author(s): Matheson; Tarjan

Conjecture   Every sufficiently large plane triangulation has a dominating set of size .

Keywords: coloring; domination; multigrid; planar graph; triangulation

Double-critical graph conjecture ★★

Author(s): Erdos; Lovasz

A connected simple graph is called double-critical, if removing any pair of adjacent vertexes lowers the chromatic number by two.

Conjecture   is the only -chromatic double-critical graph

Keywords: coloring; complete graph

Counting 3-colorings of the hex lattice ★★

Author(s): Thomassen

Problem   Find .

Keywords: coloring; Lieb's Ice Constant; tiling; torus

4-regular 4-chromatic graphs of high girth ★★

Author(s): Grunbaum

Problem   Do there exist 4-regular 4-chromatic graphs of arbitrarily high girth?

Keywords: coloring; girth

Coloring random subgraphs ★★

Author(s): Bukh

If is a graph and , we let denote a subgraph of where each edge of appears in with independently with probability .

Problem   Does there exist a constant so that ?

Keywords: coloring; random graph

Hedetniemi's Conjecture ★★★

Author(s): Hedetniemi

Conjecture   If are simple finite graphs, then .

Here is the tensor product (also called the direct or categorical product) of and .

Degenerate colorings of planar graphs ★★★

Author(s): Borodin

A graph is -degenerate if every subgraph of has a vertex of degree .

Conjecture   Every simple planar graph has a 5-coloring so that for , the union of any color classes induces a -degenerate graph.

Keywords: coloring; degenerate; planar