Majority 3-edge-coloring conjecture for graphs without pendant edges
Majority 3-edge-coloring conjecture for graphs without pendant edges
A majority -edge-coloring of a graph is an edge-coloring with three colors in which, at every vertex, the number of incident edges of its most frequent color is at most the number of incident edges having other colors. A graph is Class if its chromatic index exceeds its maximum degree. Majority 3-edge-coloring conjecture. Every graph without pendant edges admits a majority -edge-coloring unless contains, as an induced subgraph, a Class graph with and with some vertices of having degree at most in . The conjecture identifies subcubic Class subgraphs as the only obstruction to majority -edge-colorability, extending the finite-graph conjecture to infinite graphs.
Sources & referencesView supporting material
Primary source
Rafał Kalinowski, Monika Pilśniak and Marcin Stawiski, “List majority edge-colorings of graphs”, arXiv:2312.00922 (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.