Total coloring conjecture for certain classes of graphs (Q2283827)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Total coloring conjecture for certain classes of graphs |
scientific article |
Statements
Total coloring conjecture for certain classes of graphs (English)
0 references
13 January 2020
0 references
Summary: A total coloring of a graph \(G\) is an assignment of colors to the elements of the graph \(G\) such that no two adjacent or incident elements receive the same color. The total chromatic number of a graph \(G\), denoted by \(\chi^{\prime\prime}(G)\), is the minimum number of colors that suffice in a total coloring. \textit{M. Behzad} [Graphs and their chromatic numbers. East Lansing, MI: Michigan State University (PhD Thesis) (1965); in: Combinatorial mathematics and its applications. Proceedings of a conference, held at the Mathematical Institute, Oxford, from 7--10 July, 1969. London-New York: Academic Press. 1--8 (1971; Zbl 0221.05062)] and \textit{V. G. Vizing} [Russ. Math. Surv. 23, No. 6, 125--141 (1968; Zbl 0192.60502); translation from Usp. Mat. Nauk 23, No. 6(144), 117--134 (1968)] conjectured that for any graph \(G, \Delta(G) + 1 \leq \chi^{\prime\prime}(G) \leq \Delta(G) + 2\), where \(\Delta(G)\) is the maximum degree of \(G\). In this paper, we prove the total coloring conjecture for certain classes of graphs of deleted lexicographic product, line graph and double graph.
0 references
total coloring
0 references
lexicographic product
0 references
deleted lexicographic product
0 references
line graph
0 references
double graph
0 references