×

On the total and AVD-total coloring of graphs. (English) Zbl 1510.05084

Summary: A total coloring of a graph \(G\) is an assignment of colors to the vertices and the edges such that (i) no two adjacent vertices receive same color, (ii) no two adjacent edges receive same color, and (iii) if an edge \(e\) is incident on a vertex \(v\), then \(v\) and \(e\) receive different colors. The least number of colors sufficient for a total coloring of graph \(G\) is called its total chromatic number and denoted by \(\chi^{\prime \prime } (G)\). An adjacent vertex distinguishing (AVD)-total coloring of \(G\) is a total coloring with the additional property that for any adjacent vertices \(u\) and \(v\), the set of colors used on the edges incident on \(u\) including the color of \(u\) is different from the set of colors used on the edges incident on \(v\) including the color of \(v\). The adjacent vertex distinguishing (AVD)-total chromatic number of \(G, \chi^{\prime \prime }_a (G)\) is the minimum number of colors required for a valid AVD-total coloring of \(G\). It is conjectured that \(\chi^{\prime \prime } (G) \leq \Delta (G) +2\), which is known as total coloring conjecture and is one of the famous open problems. A graph for which the total coloring conjecture holds is called totally colorable graph. The problem of deciding whether \(\chi^{\prime \prime } (G)= \Delta (G) +1\) or \(\chi^{\prime \prime } (G = \Delta (G)+2\) for a totally colorable graph \(G\) is called the classification problem for total coloring. However, this classification problem is known to be NP-hard even for bipartite graphs. In this paper, we give a sufficient condition for a bipartite biconvex graph \(G\) to have \(\chi^{\prime \prime } (G) = \Delta (G) +1\). Also, we propose a linear time algorithm to compute the total chromatic number of chain graphs, a proper subclass of biconvex graphs. We prove that the total coloring conjecture holds for the central graph of any graph. Finally, we obtain the AVD-total chromatic number of central graphs for basic graphs such as paths, cycles, stars and complete graphs.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Behzad, M., Graphs and their chromatic numbers (1965), Dept. of Mathematics, Michigan State University, Michigan
[2] Bojarshinov, V., Edge and total coloring of interval graphs, Discrete Appl. Math., 114, 1-3, 23-28 (2001) · Zbl 0996.05052
[3] Chen, B.-L.; Fu, H.-L.; Ko, M. T., Total chromatic number and chromatic index of split graphs, J. Combin. Math. Combin. Comput., 17, 137 · Zbl 0819.05026
[4] Chen, M.; Guo, X., Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes, Inf. Process. Lett., 109, 12, 599-602 (2009) · Zbl 1197.05045
[5] Chen, X., On the adjacent vertex distinguishing total coloring numbers of graphs with Δ = 3, Discrete Math., 308, 17, 4003-4007 (2008) · Zbl 1203.05052
[6] De Figueiredo, C. M.; Meidanis, J.; de Mello, C. P., Total-chromatic number and chromatic index of dually chordal graphs, Inf. Process. Lett., 70, 3, 147-152 (1999) · Zbl 1339.05151
[7] Hilton, A. J., The total chromatic number of nearly complete bipartite graphs, J. Combin. Theory, Ser. B, 52, 1, 9-19 (1991) · Zbl 0743.05022
[8] Hulgan, J., Concise proofs for adjacent vertex-distinguishing total colorings, Discrete Math., 309, 8, 2548-2550 (2009) · Zbl 1221.05143
[9] Machado, R. C.; de Figueiredo, C. M., Total chromatic number of unichord-free graphs, Discrete Appl. Math., 159, 16, 1851-1864 (2011) · Zbl 1228.05157
[10] McDiarmid, C. J.; Sánchez-Arroyo, A.; URL, Total colouring regular bipartite graphs is np-hard, Discrete Math., 124, 1-3, 155-162 (1994) · Zbl 0791.05042
[11] Papaioannou, A.; Raftopoulou, C., On the avdtc of 4-regular graphs, Discrete Math., 330, 20-40 (2014) · Zbl 1295.05109
[12] Pedrotti, V.; de Mello, C. P., Adjacent-vertex-distinguishing total coloring of indifference graphs, Matemática Contemporânea, 39, 101-110 (2010) · Zbl 1251.05061
[13] Total coloring of central graphs of a path, a cycle and a star, Int. J. Sci. Innov. Math. Res., 5, 10, 15-22 (2017)
[14] Vizing, V. G., Some unsolved problems in graph theory, Russ. Math. Surv., 23, 6, 125-141 (1968) · Zbl 0192.60502
[15] Wang, H., On the adjacent vertex-distinguishing total chromatic numbers of the graphs with Δ (G)= 3, J. Comb. Optim., 14, 1, 87-109 (2007) · Zbl 1125.05043
[16] Wang, W.; Huang, D.,, The adjacent vertex distinguishing total coloring of planar graphs, J. Comb. Optim., 27, 2, 379-396 (2014) · Zbl 1319.90076
[17] Wang, Y.; Wang, W., Adjacent vertex distinguishing total colorings of outerplanar graphs, J. Comb. Optim., 19, 2, 123-133 (2010) · Zbl 1216.05039
[18] Zhang, Z., On adjacent-vertex-distinguishing total coloring of graphs, Sci. China Ser. A, 48, 3, 289-299 (2005) · Zbl 1080.05036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.