PreprintCC BY 4.0arXiv
Adjacent vertex distinguishing total chromatic number of graph products
Abstract
The adjacent vertex distinguishing (AVD)-total chromatic number χ''a(G) of a graph G is the least integer k for which G has a proper total coloring f with k colors such that CG(u)≠ CG(v) for every edge uv∈ E(G), where CG(u)={f(u)}∪{f(uw):uw∈ E(G)}. The AVD-total coloring conjecture (AVD-TCC) asserts that χ''a(G)≤ Δ(G)+3 for every simple graph G, where Δ(G) is the maximum degree of G. In this paper, we prove the AVD-TCC for certain classes of graph products, including Cartesian products, lexicographic products, skew products, cover products, comb products, and Indu--Bala products.
Related
BibTeX
@misc{banerjee2026adjacent,
title = {{Adjacent vertex distinguishing total chromatic number of graph products}},
author = {Amitayu Banerjee and Jayabalan Geetha and Kanagasabapathi Somasundaram},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03411},
eprint = {2609.03411},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03411},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Adjacent vertex distinguishing total chromatic number of graph products
AU - Amitayu Banerjee
AU - Jayabalan Geetha
AU - Kanagasabapathi Somasundaram
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.03411
UR - https://arxiv.org/abs/2609.03411
AB - The adjacent vertex distinguishing (AVD)-total chromatic number χ''_a(G) of a graph G is the least integer k for which G has a proper total coloring f with k colors such that C_G(u)≠ C_G(v) for every edge uv∈ E(G), where C_G(u)={f(u)}∪{f(uw):uw∈ E(G)}. The AVD-total coloring conjecture (AVD-TCC) asserts that χ''_a(G)≤ Δ(G)+3 for every simple graph G, where Δ(G) is the maximum degree of G. In this paper, we prove the AVD-TCC for certain classes of graph products, including Cartesian products, lexicographic products, skew products, cover products, comb products, and Indu--Bala products.
ER -