Total coloring of (sub)cubic Halin graphs

Read full text Summarise with VIRAT
Authors: František Kardoš, Matúš Matok
Cited by: 0
References: 20

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Total coloring of a graph is a coloring of its vertices and edges such that adjacent or incident elements receive distinct colors. Total coloring conjecture (stipulating that the total chromatic number of a graph $G$ is at most $Δ(G)+2$) is known to be true for subcubic graphs -- five colors are always enough. However, deciding whether a total coloring with only four colors exists remains a difficult problem, even in the class of bipartite cubic graphs. We solve the problem completely for cubic and subcubic Halin graphs, proving that there are only finitely many such graphs requiring five colors.

Fields of Study & Subjects

Graph Labeling and Dimension Problems Advanced Graph Theory Research Complexity and Algorithms in Graphs

Publication details

Journal / source
arXiv (Cornell University)
Publication date
24 March 2026
Language
EN
Document type
Preprint