Adjacent vertex distinguishing total coloring of the corona product of graphs

Verma, Shaily  ; Panda, B. S.

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 317-335

Résumé

An adjacent vertex distinguishing (AVD-)total coloring of a simple graph G is a proper total coloring of G such that for any pair of adjacent vertices u and v, we have C(u) C(v), where C(u) is the set of colors given to vertex u and the edges incident to u for u∈ V(G). The AVD-total chromatic number, χ_a^” (G), of a graph G is the minimum number of colors required for an AVD-total coloring of G. The AVD-total coloring conjecture states that for any graph G with maximum degree Δ, χ_a^” (G) ≤Δ+3. The total coloring conjecture states that for any graph G with maximum degree Δ, χ^” (G) ≤Δ+2, where χ^” (G) is the total chromatic number of G, that is, the minimum number of colors needed for a proper total coloring of G. A graph G is said to be AVD-total colorable (total colorable) graph, if G satisfies the AVD-total coloring conjecture (total coloring conjecture). In this paper, we prove that for any AVD-total colorable graph G and any total-colorable graph H with Δ(H)≤Δ(G), the corona product G∘ H of G and H satisfies the AVD-total coloring conjecture. We also prove that the graph G∘ K_n admits an AVD-total coloring using (Δ(G∘ K_n)+p) colors, if there is an AVD-total coloring of graph G using (Δ(G)+p) colors, where p∈{1,2,3}. Furthermore, given a total colorable graph G and positive integer r and p where 1≤ p≤ 3, we classify the corona graphs G^(r)=G∘ G∘⋯∘ G (r+1 ) such that χ_a^” (G^(r))=Δ(G^(r))+p.

Détail

Keywords: adjacent vertex distinguishing total coloring, corona products