





















Independently posed by Behzad and Vizing, the Total Coloring Conjecture asserts that the total chromatic number of a simple connected graph $G$ is either $Δ(G)+1$ or $Δ(G)+2$, where $Δ(G)$ is the largest degree of any vertex of $G$. To decide whether a cubic graph $G$ has total chromatic number $Δ(G)+1$, even for bipartite cubic graphs, is NP-hard. The resulting problems and research persist even for total colorings that are equitable, namely with the cardinalities of the color classes differing at most by 1. Williams and Holroyd gave a new condition to solve total coloring problems via the introduction of semi-total colorings. We focus on how to obtain equitable total colorings of symmetric cubic graphs and cage graphs by means of a variation of Kempe'a 1879 graph-coloring algorithm. Such variation takes semi-total colorings to equitable ones.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。