Bordeaux 3-color conjecture and 3-choosability

A graph \(G = (V,E)\) is list \(L\)-colorable if for a given assignment \(L = \{ L(v) \mid v \in V\}\) there is a proper coloring of the vertices where each vertex gets a color in its list. The graph is \(k\)-choosable if it is list \(L\)-colorable for every possible list assignment of \(k\) colors per vertex. Thomasson proved that every planar graph of girth 5 is 3-choosable, and Gunter proved that determining if a planar graph is 3-choosable is NP-complete. Many authors have examined conditions on short cycles in plane graphs that imply it is 3-choosable. In this paper the authors show: (1) Any planar graph without 4- and 5-cycles, and without triangles of distance less than 4 is 3-choosable. (2) Any planar graph without 4-, 5-, and 6-cycles and without triangles of distance less than 3 is 3-choosable. In contrast, (3) there exists a non-3-choosable graph without 4- or 5-cycles and without intersecting triangles. The Bordeaux 3-color conjecture is: Every planar graph without intersecting triangles and without 5-cycles is 3-colorable. The authors' third result shows that the Bordeaux 3-color conjecture is false for list colorings.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Bordeaux 3-color conjecture and 3-choosability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2488930)