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
Mazzuoccolo, Giuseppe;
2016-01-01
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?File | Dimensione | Formato | |
---|---|---|---|
Sasaki_etal_new_CTW13_240913.pdf
accesso aperto
Tipologia:
Documento in Pre-print
Licenza:
Accesso ristretto
Dimensione
414.12 kB
Formato
Adobe PDF
|
414.12 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.