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?

On the equitable total chromatic number of cubic graphs / Dantas, S.; de Figueiredo, C. M. H.; Mazzuoccolo, Giuseppe; Preissmann, M.; dos Santos, V. F.; Sasaki, D.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 209:(2016), pp. 84-91. [10.1016/j.dam.2015.10.013]

### On the equitable total chromatic number of cubic graphs

#### Abstract

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?
##### Scheda breve Scheda completa Scheda completa (DC)
2016
209
84
91
On the equitable total chromatic number of cubic graphs / Dantas, S.; de Figueiredo, C. M. H.; Mazzuoccolo, Giuseppe; Preissmann, M.; dos Santos, V. F.; Sasaki, D.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 209:(2016), pp. 84-91. [10.1016/j.dam.2015.10.013]
Dantas, S.; de Figueiredo, C. M. H.; Mazzuoccolo, Giuseppe; Preissmann, M.; dos Santos, V. F.; Sasaki, D.
File in questo prodotto:
File
Sasaki_etal_new_CTW13_240913.pdf

Accesso riservato

Dimensione 414.12 kB