Research PaperNo Access

Total coloring of quasi-line graphs and inflated graphs

S. Mohan

Department of Mathematics, Amrita School of Engineering, Amrita Vishwa Vidyapeetham, Coimbatore, India

Department of Mathematics, School of Engineering, Presidency University, Bengaluru, India

E-mail Address: smohanmat@gmail.com

Search for more papers by this author

J. Geetha

Department of Mathematics, Amrita School of Engineering, Amrita Vishwa Vidyapeetham, Coimbatore, India

E-mail Address: j_geetha@cb.amrita.edu

Search for more papers by this author

, and

K. Somasundaram

Department of Mathematics, Amrita School of Engineering, Amrita Vishwa Vidyapeetham, Coimbatore, India

E-mail Address: s_sundaram@cb.amrita.edu

Search for more papers by this author

https://doi.org/10.1142/S1793830921500609Cited by:3 (Source: Crossref)

Abstract

A total coloring of a graph is an assignment of colors to all the elements (vertices and edges) of the graph such that no two adjacent or incident elements receive the same color. A claw-free graph is a graph that does not have $K_{1, 3}$ $K_{1, 3}$ as an induced subgraph. Quasi-line and inflated graphs are two well-known classes of claw-free graphs. In this paper, we prove that the quasi-line and inflated graphs are totally colorable. In particular, we prove the tight bound of the total chromatic number of some classes of quasi-line graphs and inflated graphs.

Keywords:

AMSC: 05C15

References

1. M. Behzad, Graphs and their chromatic numbers, Doctoral Thesis, Michigan State University (1965). Google Scholar
2. M. Chudnovsky and A. O. Fradkin , Hadwiger’s conjecture for quasi-line graphs, J. Graph Theory 59(1) (2008) 17–33. Crossref, Google Scholar
3. M. Chudnovsky and P. Seymour , The structure of claw-free graphs, in Surveys in Combinatorics 2005, London Mathematical Society Lecture Note Series, Vol. 327 (Cambridge University Press, 2005), pp. 153–172. Crossref, Google Scholar
4. V. Chvátal and N. Sbihi , Recognizing claw-free Berge graphs, J. Combinatorial Theory, Ser. B 44 (1988) 154–176. Crossref, Google Scholar
5. J. H. Colin McDiarmid and A. Sanchez-Arroyo , Total coloring regular bipartite graphs is NP-hard, Discrete Math. 124 (1994) 155–162. Crossref, Google Scholar
6. F. Eisenbrand, G. Oriolo, G. Stauffer and P. Ventura , The stable set polytope of quasi-line graphs, Combinatorica 28(1) (2008) 45–67. Crossref, Google Scholar
7. O. Favaron , Inflated graphs with equal independence number and upper irredundance number, Discrete Math. 236 (2001) 81–94. Crossref, Google Scholar
8. R. Giles and L. E. Trotter , On stable set polyhedra for $K_{1, 3}$ $K_{1, 3}$ -free graphs, J. Combinatorial Theory, Ser. B 31 (1981) 313–326. Crossref, Google Scholar
9. A. J. W. Hilton and H. R. Hind , Total chromatic number of graphs having large maximum degree, Discrete Math. 117(1–3) (1993) 127–140. Crossref, Google Scholar
10. A. V. Kostochka , The total coloring of a multigraph with maximal degree four, Discrete Math. 17(2) (1977) 161–163. Crossref, Google Scholar
11. A. V. Kostochka, Upper bounds of chromatic functions on graphs (in Russian), Doctoral Thesis, Novosibirsk (1978). Google Scholar
12. 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. Crossref, Google Scholar
13. F. Maray and B. Reed , A description of claw-free perfect graphs, J. Combinatorial Theory, Ser. B 75 (1999) 134–156. Crossref, Google Scholar
14. M. Rosenfeld , On the total coloring of certain graphs, Israel J. Math. 9(3) (1971) 396–402. Crossref, Google Scholar
15. A. Sanchez-Arroyo , Determining the total colouring number is NP-hard, Discrete Math. 78 (1989) 315–319. Crossref, Google Scholar
16. N. Vijayaditya , On total chromatic number of a graph, J. London Math. Soc. 3(2) (1971) 405–408. Crossref, Google Scholar
17. 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. Google Scholar
18. H. P. Yap and K. H. Chew , The chromatic number of graphs of high degree, II, J. Austral. Math. Soc., Ser. A 47 (1989) 445–452. Crossref, Google Scholar