Total-coloring extension conjecture for matchings
Total-coloring extension conjecture for matchings
Let be a graph with maximum degree , and let be a subgraph of . A matching is a subgraph consisting of vertex-disjoint copies of . A total--coloring of in is a total--coloring that is proper with respect to .
Total-coloring extension conjecture for matchings. If is a matching, then every total--coloring of in extends to a total--coloring of .
The conjecture asks whether the number of preassigned colors can be reduced from the general greedy bound to without restrictions on the ambient graph or the matching. The paper proves the assertion for planar graphs when , and notes that is best possible in general.
Sources & referencesView supporting material
Primary source
Owen Henderschedt and Jessica McDonald, “Extending total colorings in planar graphs”, arXiv:2509.18940 (2025).
Additional references
2 papers in this index state this conjecture (2021–2025). The statement above is taken from the most recent of them; the others are arXiv:2112.13334.
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.