Poor-edge conjecture for normal colorings of bridgeless cubic graphs
Poor-edge conjecture for normal colorings of bridgeless cubic graphs
Let be a bridgeless cubic graph. Let be the set of all normal -colorings of , and, assuming this set is nonempty, let be the maximum number of poor edges among colorings in . Let be the Petersen graph and let be the graph obtained from by truncating one vertex. Poor-edge conjecture. If , then
Moreover, if , then
The claim refines the Petersen Coloring Conjecture by predicting unavoidable poor edges in normal -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
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.