Structural reformulation of the 3-colorability conjecture for G2{\cal G}_2

Let G{\cal G}_{\ell} be the family of graphs with girth 2+12\ell+1 and with no odd holes of length at least 2+32\ell+3. Let θ+\theta^+ be the graph obtained from the Petersen graph by removing two adjacent vertices, let θ\theta be obtained from θ+\theta^+ by removing an edge incident with two 3-vertices, and let θ\theta^- be obtained from the Petersen graph by removing three vertices that induce a path.

Structural reformulation. Graphs in G0{\cal G}_0 induce neither θ\theta nor θ\theta^- .

This is presented as an equivalent reformulation of the earlier 3-colorability conjecture after reducing graphs in G2{\cal G}_2 that contain two edge-sharing 55-cycles to the configurations θ\theta and θ\theta^-. The supplied material does not state whether this reformulation has been resolved.

Sources & referencesView supporting material

Primary source

Di Wu, Baogang Xu and Yian Xu, “On coloring of graphs of girth 2l + 1 without longer odd holes”, arXiv:2204.06284 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.