Poor-edge conjecture for normal colorings of bridgeless cubic graphs

Let GG be a bridgeless cubic graph. Let NC(G)\mathrm{NC}(G) be the set of all normal 55-colorings of GG, and, assuming this set is nonempty, let poor(G)\mathrm{poor}(G) be the maximum number of poor edges among colorings in NC(G)\mathrm{NC}(G). Let P10P_{10} be the Petersen graph and let P10ΔP_{10}^{\Delta} be the graph obtained from P10P_{10} by truncating one vertex. Poor-edge conjecture. If GP10G\ne P_{10}, then

poor(G)>0.\mathrm{poor}(G)>0.

Moreover, if GP10,P10ΔG\ne P_{10},P_{10}^{\Delta}, then

poor(G)6.\mathrm{poor}(G)\ge 6.

The claim refines the Petersen Coloring Conjecture by predicting unavoidable poor edges in normal 55-colorings, with stronger lower bounds away from the Petersen graph and its one-vertex truncation. The paper presents it as a proposed direction based on observations about small snarks and the constructions studied there.

Sources & referencesView supporting material

Primary source

Jelena Sedlar and Riste Škrekovski, “Normal 5-edge-coloring of some snarks superpositioned by the Petersen graph”, arXiv:2305.05981 (2023).

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.