Total coloring conjecture on certain classes of product graphs

Kanagasabapathi Somasundaram, Jayabalan Geetha, Radhakrishnan Vignesh

Abstract


A total coloring of a graph G is an assignment of colors to the elements of the graph G such that no adjacent vertices and edges receive the same color. The total chromatic number of a graph G, denoted by χ″(G), is the minimum number of colors that suffice in a total coloring. Behzad and Vizing conjectured that for any graph G, Δ(G)+1 ≤ χ″(G)≤Δ(G)+2, where Δ(G) is the maximum degree of G. In this paper, we prove the Behzad and Vizing conjecture for Indu - Bala product graph, Skew and Converse Skew product graph, Cover product graph, Clique cover product graph and Comb product graph.

Keywords


total coloring, Indu-Bala product, skew and converse skew product, cover product, clique cover product, comb product

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2023.11.1.18

References

L. Accardi, A. B. Ghorbal and N. Obata, Monotone Independence, Comb graphs and Bose-Einstein Condensation, Infinite Dimensional Analysis, Quantum Probability and Related Topics, 7 (3) (2004), 419–435.

M. Behzad, Graphs and their chromatic numbers, Doctoral Thesis, Michigan State University, (1965).

O. V. Borodin, On the total colouring of planar graphs, J. Reine Angew. Math. 394 (1989), 180–185.

J. H. Colin McDiarmid and A. S. Arroyo, Total coloring regular bipartite graphs is NP-hard, Discrete Math. 124 (1994), 155–162.

Z. Duan, P. Lv, L. Miao, Z. Miao, Cu. Wang, New upper bounds on the L(2, 1)-labeling of the skew and converse skew product graphs, Theoretical Computer Science. 412 (2011), 2393–2397.

A. J. W. Hilton and H. R. Hind, Total chromatic number of graphs having large maximum degree, Discrete Math. (1-3) 117 (1993), 127–140.

A. M. Hinz and D. Parisse, Coloring Hanoi and Sierpi$acute{text n}$ski graphs, Discrete Math. (9) 312 (2012), 1521–1535.

W. Imrich and S. Klav$check{text z}$ar, Product Graphs: Structure and Recognition, Wiley, New york, (2000).

G. Indulal and R. Balakrishnan, Distance spectrum of Indu - Bala product of graphs, AKCE International Journal of Graphs and Combinatorics 13 (2016), 230 –234.

J. Harrelson and H. Reavis, Maximum average degree of list-edge-critical graphs and Vizing’s conjecture, Electron. J. Graph Theory Appl. 10 (2) (2022), 385–392.

J. Tolentino, R. Marcelo, M.A. Tolentino, Electron. J. Graph Theory Appl. 10 (1) (2022), 131–149.

A. V. Kostochka, The total coloring of a multigraph with maximal degree four, Discrete Math. 17 (2) (1977), 161–163.

A. V. Kostochka, The total chromatic number of any multigraph with maximum degree five is at most seven, Discrete Math., 162 (1-3) (1996), 199–214.

A. Llamas and J. M. Bernal, Cover Product and Betti Polynomial of Graphs, Canad.Math.Bull, 58 (2) (2015), 320–333.

M. Pil$acute{text s}$niak and M. Wo$acute{text z}$niak On the adjacent vertex distinguishing index by sums in total proper colorings, Preprint Nr MD 051, to appear in Graphs Comb.

M. Rosenfeld, On the total coloring of certain graphs, Israel J. Math. 9 (3) (1971), 396–402.

TP Sandhiya, J. Geetha and K. Somasundaram, “Total colrings of certain classes of lexicography product graphs” Discrete Mathematics, Algorithms and Applications, 14 (3) (2022), 2150129.

Y. Shibata and Y. Kikuchi, Graph products based on the distance in graphs, IEICE Trans. Fundam. 83 (3) (2000), 459–464.

Z. D. Shao and D. Zhang. Improved upper bounds on the L(2,1)-labelling of the skew and converse skew product graphs, Theoret. Comput. Sci. 400 (2008).

R. Vignesh, J. Geetha and K. Somasundaram, Total Coloring Conjecture for Vertex, Edge and Neighborhood Corona Products of Graphs, Discrete Mathematics, Algorithms and Applications, 11 (1) (2019), 1950014 (1-9).

R. Vignesh, J. Geetha and K. Somasundaram, Total Coloring Conjecture for Certain Classes of Graphs, Algorithms 11 (2018), 161 (1-7).

N. Vijayaditya, On total chromatic number of a graph, J. London Math. Soc. 3 (2) (1971), 405–408.

V. G. Vizing, Some unsolved problems in graph theory(in Russian), Uspekhi Mat. Nauk. (23) 117-134, English translation in Russian Math. Surveys 23 (1968), 125–141.

H. P. Yap and K. H. Chew, The chromatic number of graphs of high degree, II, J. Austral. Math. Soc., (Series- A) 47 (1989), 445–452.

H. P. Yap, Total Colourings of Graphs, Lecture Notes in Mathematics, Springer, Berlin,1623 (1996).

B. X. Zhu, Clique cover product and unimodality of independence polynomials, Discrete Applied Mathematics 206 (2016),172–180.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats