The eventual fractional-defect conjecture for connected 4-regular graphs
The eventual fractional-defect conjecture for connected 4-regular graphs
A graph is -regular if every vertex has degree . For a graph , let denote the minimum defect in a fractional -coloring. The exceptional graphs are the compositions of odd cycles with the independent graph on two vertices. Eventual fractional-defect conjecture for connected -regular graphs. Apart from where is odd, it holds that
for all but finitely many connected -regular graphs.
Lovász's result gives the general upper bound for -regular graphs. The exceptional odd-cycle compositions attain , 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
Sign in to submit a solution.
No solutions have been posted yet.