z-logo
open-access-imgOpen Access
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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom