| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 418459 | Discrete Applied Mathematics | 2016 | 8 Pages |
A total coloring is equitable if the number of elements colored with each color differs by at most one, and the least integer for which a graph has such a coloring is called its equitable total chromatic number. Wang conjectured that the equitable total chromatic number of a multigraph of maximum degree ΔΔ is at most Δ+2Δ+2, and proved this for the case where Δ≤3Δ≤3. Therefore, the equitable total chromatic number of a cubic graph is either 4 or 5, and in this work we prove that the problem of deciding whether it is 4 is NP-complete for bipartite cubic graphs.Furthermore, we present the first known Type 1 cubic graphs with equitable total chromatic number 5. All of them have, by construction, a small girth. We also find one infinite family of Type 1 cubic graphs of girth 5 having equitable total chromatic number 4. This motivates the following question: Does there exist Type 1 cubic graphs of girth greater than 5 and equitable total chromatic number 5?
