2025/09/23 by Owen Henderschedt, Henderschedt, Owen, Jessica McDonald +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2509.18940
We initiate the study of total-coloring extensions, and focus our attention on planar graphs, asking: ``When can a total-k-coloring of some subgraph H of a planar graph G be extended to a total-k-coloring of G?'' We prove that if H is a matching, then any total-(Δ+3)-coloring of H in G extends to G provided Δ≥ 28; this number of colors is best-possible without introducing a distance condition on H. We also prove that if H is a set of distance-3 cliques then any total-(Δ+1)-coloring of H extends to G provided Δ≥ 27; this distance condition cannot be lowered.