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

About 4 years old · traced to

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.

References

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.