Total-coloring extension conjecture for matchings

Let GG be a graph with maximum degree Δ\Delta, and let HH be a subgraph of GG. A matching is a subgraph consisting of vertex-disjoint copies of K2K_2. A total-kk-coloring of HH in GG is a total-kk-coloring that is proper with respect to GG.

Total-coloring extension conjecture for matchings. If HH is a matching, then every total-(Δ+3)(\Delta+3)-coloring of HH in GG extends to a total-(Δ+3)(\Delta+3)-coloring of GG.

The conjecture asks whether the number of preassigned colors can be reduced from the general greedy bound 2Δ+12\Delta+1 to Δ+3\Delta+3 without restrictions on the ambient graph or the matching. The paper proves the assertion for planar graphs when Δ28\Delta\geq 28, and notes that Δ+3\Delta+3 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

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.