Equitable Total Chromatic Number of K× for p Even
Author(s) -
Anderson G. da Silva,
Simone Dantas,
Diana Sasaki
Publication year - 2019
Publication title -
electronic notes in theoretical computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.242
H-Index - 60
ISSN - 1571-0661
DOI - 10.1016/j.entcs.2019.08.060
Subject(s) - combinatorics , mathematics , conjecture , graph , total coloring , chromatic scale , discrete mathematics , list coloring , domination analysis , brooks' theorem , graph power , line graph , vertex (graph theory)
A total coloring is equitable if the number of elements colored by any two distinct colors differs by at most one. The equitable total chromatic number of a graph ( χ e ″ ) is the smallest integer for which the graph has an equitable total coloring. Wang (2002) conjectured that Δ + 1 ≤ χ e ″ ≤ Δ + 2 . In 1994, Fu proved that there exist equitable (Δ + 2)-total colorings for all complete r-partite p-balanced graphs of odd order. For the even case, he determined that χ e ″ ≤ Δ + 3 . Silva, Dantas and Sasaki (2018) verified Wang's conjecture when G is a complete r-partite p-balanced graph, showing that χ e ″ = Δ + 1 if G has odd order, and χ e ″ ≤ Δ + 2 if G has even order. In this work we improve this bound by showing that χ e ″ = Δ + 1 when G is a complete r-partite p-balanced graph with r ≥ 4 even and p even, and for r odd and p even.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom