On the AVD-total chromatic number of circulant graphs

• Matheus Adauto UFRJ
• Mauro Nigro UFRJ

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

Resumo

AVD-k-total coloring of a simple graph G is a mapping π : V (G) ∪ E(G) → {1, . . ., k} such that: adjacent or incident elements x, y ∈ V (G) ∪ E(G), π(x) ≠ π(y); and for each pair of adjacent vertices x, y ∈ V (G), sets {π(x)} ∪ {π(xv) | xv ∈ E(G) and v ∈ V (G)} and {π(y)} ∪ {π(yv) | yv ∈ E(G) and v ∈ V (G)} are distinct. The AVD-total chromatic number, denoted by χ′′_a(G) is the smallest k for which G admits an AVD-k-total-coloring. [Zhang et al. 2005] conjectured that any graph G has χ′′_a(G) ≤ ∆+3. [Hulgan 2009] conjectured that any subcubic graph G has χ′′_a(G) ≤ 5. In this article, we proved that all cubic circulant graph has χ′′_a(C_2n(d, n))) = 5, being positive evidence to Hulgan’s conjecture.

Referências

Alvarado, J., Dantas, S., and Marinho, R. (2019). On adjacent-vertex-distinguishing total colourings of powers of cycles, hypercubes and lattice graphs. Electron. Notes Theor. Comput. Sci., 346:41–51.

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

Chen, M. and Guo, X. (2009). Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes. Information Processing Letters, 109(12):599–602.

Chen, X. (2008). On the adjacent vertex distinguishing total coloring numbers of graphs with δ = 3. Discrete Math., 308(17):4003–4007.

Chen, X. and Zhang, Z. (2008). AVDTC numbers of generalized halin graphs with maximum degree at least 6. Acta Math. Appl. Sin. Engl. Ser., 24:55–58.

Hackmann, A. and Kemnitz, A. (2004). Circular total colorings of cubic circulant graphs. J. Combin. Math. Combin. Comput., pages 65–72.

Heuberger, C. (2003). On planarity and colorability of circulant graphs. Discrete Math., 268(1):153–169.

Hulgan, J. (2009). Concise proofs for adjacent vertex-distinguishing total colorings. Discrete Math., 309(8):2548–2550.

Hulgan, J. (2010). Graph coloring with constraints. PhD thesis, University of Memphis.

Luiz, A. G., Campos, C., and de Mello, C. (2015). AVD-total-colouring of complete equipartite graphs. Discrete Appl. Math., 184:189–195.

Luiz, A. G., Campos, C., and de Mello, C. (2017). AVD-total-chromatic number of some families of graphs with δ(g) = 3. Discrete Appl. Math., 217:628–638.

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

Papaioannou, A. and Raftopoulou, C. (2014). On the AVDTC of 4-regular graphs. Discrete Math., 330:20–40.

Verma, S., Fu, H.-L., and S. Panda, B. (2022). Adjacent vertex distinguishing total coloring in split graphs. Discrete Math., 345(11).

Verma, S. and Panda, B. S. (2022). Adjacent vertex distinguishing total coloring of the corona product of graphs. Discuss. Math. Graph Theory.

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

Yap, H. P. (1996). Total colourings of graphs. Springer, Berlin.

Zhang, Z., Chen, X., and Li, J. (2005). On adjacent-vertex-distinguishing total coloring of graphs. Sci. China Ser. A-Math., 48:289–299.

Zhu, E., Jiang, F., Li, Z., Shao, Z., and Xu, J. (2016). On adjacent vertex-distinguishing total chromatic number of generalized petersen graphs. In 2016 IEEE First International Conference on Data Science in Cyberspace (DSC), pages 230–234.