Processing math: 100%

A 2-fold coloring of a graph G assigns a set of two colors to each vertex such that adjacent vertices get disjoint sets. We get a weakened version of the Borodin-Kostochka conjecture if instead of requiring a (Δ(G)1)-coloring, we require a 2-fold coloring from a pot of 2Δ(G)1 colors. A minimal counterexample to this conjecture cannot have any of the graphs here as induced subgraphs (these are (2d(v)1:2)-choosable graphs, actually online-choosable). In the pictures, i gave different colors to the components of the complement so it is easier to see the joins. Notice how severely restricted these require neighborhoods to be for minimal counterexamples. For 3-fold and 4-fold coloring, things get even more restricted.