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

From papers

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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.