The eventual fractional-defect conjecture for connected 4-regular graphs

About 9 years old · traced to

A graph GG is 44-regular if every vertex has degree 44. For a graph GG, let D(G,2)D(G,2) denote the minimum defect in a fractional 22-coloring. The exceptional graphs are the compositions Cm[2K1]C_m[2K_1] of odd cycles with the independent graph on two vertices. Eventual fractional-defect conjecture for connected 44-regular graphs. Apart from G=Cm[2K1]G=C_m[2K_1] where mm is odd, it holds that

D(G)<2D(G)<2

for all but finitely many connected 44-regular graphs.

Lovász's result gives the general upper bound D(G,2)≤2D(G,2)\le 2 for 44-regular graphs. The exceptional odd-cycle compositions attain D(G,2)=2D(G,2)=2, while computational searches support strict inequality for many other graphs; the conjecture asserts that only finitely many connected exceptions remain beyond those compositions.

References

Primary source

Wayne Goddard and Honghai Xu, “Colorings with Fractional Defect”, arXiv:1702.01442 (2019).

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.