On the AVD-Total Chromatic Number of 4-Regular Circulant Graphs
DOI:
https://doi.org/10.5540/03.2026.012.01.0322Palavras-chave:
Total Coloring, Adjacent-Vertex-Distinguishing, Circulant GraphsResumo
Abstract. An AVD-k-total coloring of a simple graph G is a mapping π : V(G)∪E(G) → {1, . . . , k}, with k ≥ 1 such that: for each pair of 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. In 2005, Zhang et al. conjectured that any graph G has χ''a(G) ≤ Δ+ 3, where Δ is the maximum degree of G and this conjecture is known as AVD-Total Coloring Conjecture (AVD-TCC). In this article, we determine that the AVD-total chromatic number of two infinite families of 4-regular circulant graphs, we prove that χ''a(Cn(a, b)) = 6, where n is even and a, b are both odd such that 1 ≤ a < b < ⌊n/2⌋, and χ''a(Cn(1, k)) = 6, where n and ℓ = n/gcd(n,k) are even.
Downloads
Referências
M. Adauto and M. Nigro. “On the AVD-total chromatic number of circulant graphs”. In: Anais do IX Encontro de Teoria da Computação. Brasília/DF: SBC, 2024, pp. 95–99. DOI: 10.5753/etc.2024.2922. url: https://sol.sbc.org.br/index.php/etc/article/view/29313.
J. D. Alvarado, S. Dantas, and R. Marinho. “On Adjacent-vertex-distinguishing Total Colourings of Powers of Cycles, Hypercubes and Lattice Graphs”. In: Electron. Notes Theor. Comput. Sci. (2019). doi: https://doi.org/10.1016/j.entcs.2019.08.005.
M. Behzad. “Graphs and and their chromatic numbers”. PhD thesis. Michigan State University, 1965.
J. Bondy and U. Murty. Graph Theory. New York: Springer, 2008.
C. N. Campos and C. P. de Mello. “A result on the total colouring of powers of cycles”. In: Discret. Appl. Math. 155 (2007), pp. 585–597. doi: https://doi.org/10.1016/j.dam.2006.08.010.
C. N. Campos and C. P. de Mello. “Total colouring of C2n”. In: Tend. Math. Apl. Comput. 4 (2003), pp. 177–186. doi: https://doi.org/10.5540/tema.2003.04.02.0177.
M. Chen and X. Guo. “Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes”. In: Inf. Process. Lett. 109.12 (2009), pp. 599–602. DOI: https://doi.org/10.1016/j.ipl.2009.02.006.
X. Chen. “On the adjacent vertex distinguishing total coloring numbers of graphs with Δ = 3”. In: Discrete Math. (2008). doi: https://doi.org/10.1016/j.disc.2007.07.091.
Xe. Chen and Zf. Zhang. “AVDTC numbers of generalized Halin graphs with maximum degree at least 6.” In: Acta Math. Appl. Sin. Engl. Ser. 24 (2008), pp. 55–58. DOI: https://doi.org/10.1007/s10255-005-5222-8.
L. Faria, M. Nigro, M. Preissmann, and D. Sasaki. “Results about the total chromatic number and the conformability of some families of circulant graphs”. In: Discret. Appl. Math. 340 (2023), pp. 123–133. DOI: doi.org/10.1016/j.dam.2023.07.003.
J. Geetha, K. Somasundaram, and Hl. Fu. “Total colorings of circulant graphs”. In: Discrete Math. Algorithms Appl. (2021).
A. Hackmann and A. Kemnitz. “Circular total colorings of cubic circulant graphs”. In: J. Combin. Math. Combin. Comput. (2004), pp. 65–72.
C. Heuberger. “On planarity and colorability of circulant graphs”. In: Discrete Math. (2003). doi: https://doi.org/10.1016/S0012-365X(02)00685-4.
J. Hulgan. “Concise proofs for adjacent vertex-distinguishing total colorings”. In: Discrete Math. (2009). doi: https://doi.org/10.1016/j.disc.2008.06.002.
R. Khennoufa and O. Togni. “Total and fractional total colourings of circulant graphs”. In: Discrete Math. 308.24 (2008), pp. 6316–6329. DOI: https://doi.org/10.1016/j.disc.2007.11.070.
A. G. Luiz, C. N. Campos, and C. P. de Mello. “AVD-total-colouring of complete equipartite graphs”. In: Discrete Appl. Math. 184 (2015), pp. 189–195. DOI: https://doi.org/10.1016/j.dam.2014.11.006.
C. J. H. McDiarmid and A. Sánchez-Arroyo. “Total colouring regular bipartite graphs is NP-hard”. In: Discrete Math. 124.1 (1994), pp. 155–162. doi: https://doi.org/10.1016/0012-365X(92)00058-Y.
R. Navaneeth, J. Geetha, K. Somasundaram, and Hl. Fu. “Total colorings of some classes of four regular circulant graphs”. In: AKCE International Journal of Graphs and Combinatorics (2022). DOI: https://doi.org/10.1080/09728600.2022.2088316.
A. Papaioannou and C. Raftopoulou. “On the AVDTC of 4-regular graphs”. In: Discrete Math. 330 (2014), pp. 20–40. DOI: https://doi.org/10.1016/j.disc.2014.03.019.
S. Verma, Hl. Fu, and B. S. Panda. “Adjacent vertex distinguishing total coloring in split graphs”. In: Discrete Math. (2022). doi: https://doi.org/10.1016/j.disc.2022.113061.
S. Verma and B. S. Panda. “Adjacent vertex distinguishing total coloring of the corona product of graphs”. In: Discuss. Math. Graph Theory. (2022). DOI: https://doi.org/10.7151/dmgt.2445.
V. Vizing. “On an estimate of the chromatic class of a p-graph”. In: Metody Diskret. Analiz. (1964), pp. 25–30.
H. P. Yap. Total colourings of graphs. Berlin: Springer, 1996.
Z. Zhang, X. Chen, and J. Li. “On adjacent-vertex-distinguishing total coloring of graphs”. In: Sci. China Ser. A-Math. 48 (2005), pp. 289–299. DOI: https://doi.org/10.1360/03ys0207.
A. Zorzi. “Coloração total em grafos potência de ciclo”. Master dissertation. Rio de Janeiro: Universidade Federal do Rio de Janeiro, 2019, p. 43.
A. Zorzi, C. M. H. de Figueiredo, R. Machado, and U. S. Souza. “Even-power of Cycles With Many Vertices are Type 1 Total Colorable”. In: Electron. Notes Theor. Comput. Sci. 346 (2019), pp. 747–758. ISSN: 1571-0661. DOI: https://doi.org/10.1016/j.entcs.2019.08.065.
