Structural reformulation of the 3-colorability conjecture for
Structural reformulation of the 3-colorability conjecture for
Let be the family of graphs with girth and with no odd holes of length at least . Let be the graph obtained from the Petersen graph by removing two adjacent vertices, let be obtained from by removing an edge incident with two 3-vertices, and let be obtained from the Petersen graph by removing three vertices that induce a path.
Structural reformulation. Graphs in induce neither nor .
This is presented as an equivalent reformulation of the earlier 3-colorability conjecture after reducing graphs in that contain two edge-sharing -cycles to the configurations and . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.