The line graphs of Möbius ladder graphs are Type 1

• Luerbio Faria UERJ
• Mauro Nigro UERJ
• Diana Sasaki UERJ

DOI: https://doi.org/10.5753/etc.2024.2421

Resumo

A k-total coloring of G is an assignment of k colors to its elements (vertices and edges) such that adjacent or incident elements have distinct colors. The total chromatic number of a graph G is the smallest integer k for which G has a k-total coloring. If the total chromatic number of G is ∆(G) + 1, then we say that G is Type 1. The line graph of G, denoted by L(G), is the graph whose vertex set is the edge set of G and two vertices of the line graph of G are adjacent if the corresponding edges are adjacent in G. In this paper, we prove that the line graphs of Möbius ladder graphs, L(M_2n), are Type 1.

Referências

Behzad, M. (1965). Graphs and and their chromatic numbers. PhD thesis, Michigan State University.

Chetwynd, A. G. and Hilton, A. J. W. (1988). Some refinements of the total chromatic number conjecture. Congr. Numer., pages 195–216.

Faria, L., Nigro, M., and Sasaki, D. (2023). On the conformability of regular line graphs. RAIRO Oper. Res.

Jayaraman, G., Muthuramakrishnan, D., and Vishnu Kumar, S. (2022). Total coloring of line graph and square graph for certain graphs. Advances and Applications in Mathematical Sciences, 21(11).

Leven, D. and Galil, Z. (1983). Np completeness of finding the chromatic index of regular graphs. Journal of Algorithms, 4(1):35–44.

McDiarmid, C. J. and Sánchez-Arroyo, A. (1994). Total colouring regular bipartite graphs is np-hard. Discrete Math., 124(1):155–162.

Mohan, S., Geetha, J., and Somasundaram, K. (2021). Total coloring of quasi-line graphs and inflated graphs. Discrete Mathematics, Algorithms and Applications, 13(05).

Vignesh, R., Geetha, J., and Somasundaram, K. (2018). Total coloring conjecture for certain classes of graphs. Algorithms, 11(10).

Vizing, V. (1964). On an estimate of the chromatic class of a p-graph. Metody Diskret. Analiz., pages 25–30.