PlumX Metrics
Embed PlumX Metrics

On the equitable total chromatic number of cubic graphs

Discrete Applied Mathematics, ISSN: 0166-218X, Vol: 209, Page: 84-91
2016
  • 9
    Citations
  • 0
    Usage
  • 5
    Captures
  • 0
    Mentions
  • 0
    Social Media
Metric Options:   Counts1 Year3 Year

Metrics Details

Article Description

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, and proved this for the case where Δ≤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?

Provide Feedback

Have ideas for a new metric? Would you like to see something else here?Let us know