On the conformability of the disjoint union of graphs

• Luerbio Faria UERJ
• Mauro Nigro UERJ
• Myriam Preissmann Université Grenoble Alpes
• Diana Sasaki UERJ

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

Resumo

[Chetwynd and Hilton 1988] defined conformable vertex coloring, intending to characterize the vertex coloring induced by a (∆ + 1)-total coloring. [Sánchez-Arroyo 1989] proved that determining the total chromatic number is an NP-complete problem even for cubic bipartite graphs. In contrast, [Faria et al. 2025] proved that characterizing conformable graphs with maximum degree three is a polynomial-time problem. The definition of conformable vertex coloring introduces a dependency on the number of connected components. Therefore, the study of conformability of disjoint unions of graphs becomes relevant. In this paper, we determine how conformability behaves under disjoint union, depending on whether the components are conformable or anticonformable.

Referências

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

Campos, C. N. and de Mello, C. P. (2007). A result on the total colouring of powers of cycles. Discret. Appl. Math., 155:585–597.

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., Preissmann, M., and Sasaki, D. (2023a). Results about the total chromatic number and the conformability of some families of circulant graphs. Discret. Appl. Math., 340:123–133.

Faria, L., Nigro, M., and Sasaki, D. (2023b). On the conformability of regular line graphs. RAIRO-Operations Research.

Faria, L., Nigro, M., and Sasaki, D. (2025). A polynomial-time algorithm for conformable coloring on regular bipartite and subcubic graphs. Discret. Optim., 55:100865.

Hamilton, G. M., Hilton, A. J. W., and Hind, H. R. F. (1999). Totally critical even order graphs. J. Comb. Theory Ser. B., 76(2):262–279.

Hilton, A. J. W. and Hind, H. R. (2002). Non-conformable subgraphs of non-conformable graphs. Discrete Math., pages 203–224.

Nigro, M., Adauto, M. N., and Sasaki, D. (2021). On total coloring of 4-regular circulant graphs. Procedia Comput. Sci., 195:315–324.

Rosenfeld, M. (1971). On the total chromatic number of a graph. Israel J. Math., pages 396–402.

Sánchez-Arroyo, A. (1989). Determining the total colouring number is NP-hard. Discrete Math., pages 315–319.

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

Vijayaditya, N. (1971). On total chromatic number of a graph. J. London Math. Soc., pages 405–408.

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

Zorzi, A., Figueiredo, C., Machado, R., Zatesko, L., and Souza, U. (2022). Compositions, decompositions, and conformability for total coloring on power of cycle graphs. Discret. Appl. Math., 323:349–363.