The conformability of connected subcubic graphs
Abstract
In this paper we prove that every connected subcubic graph is conformable, except if $G$ is either complete $K_4$ or complete bipartite $K_{3,3}$. Our characterization leads to a polynomial-time algorithm.
References
Behzad, M. (1965). Graphs and and their chromatic numbers. PhD thesis, Michigan State University.
Brooks, R. L. (1941). On colouring the nodes of a network. Math. Proc. Camb. Philos. Soc., pages 194–197.
Campos, C. N. and de Mello, C. P. (2007). A result on the total colouring of powers of cycles. Discrete Appl. Math., pages 585–597.
Chetwynd, A. G. and Hilton, A. J. W. (1988). Some refinements of the total chromatic number conjecture. Congr. Numer., pages 195–216.
Hamilton, G. M., Hilton, A. J. W., and Hind, H. R. F. (1999). Totally critical even order graphs. J. Comb. Theory Ser. B., pages 262–279.
Hilton, A. J. W. and Hind, H. R. (2002). Non-conformable subgraphs of non-conformable graphs. Discrete Math., pages 203–224.
Sánchez-Arroyo, A. (1989). Determining the total colouring number is NP-hard. Discrete Math., pages 315–319.
Vizing, V. G. (1968). Some unsolved problems in graph theory. Russ. Math. Surv., pages 125–141.
Yap, H. P. (1996). Total colourings of graphs. Springer.
Zorzi, A., Figueiredo, C., Machado, R., Zatesko, L., and Souza, U. (2021). Compositions, decompositions, and conformability for total coloring on power of cycle graphs. Discrete Appl. Math. https://doi.org/10.1016/j.dam.2021.06.012.
Brooks, R. L. (1941). On colouring the nodes of a network. Math. Proc. Camb. Philos. Soc., pages 194–197.
Campos, C. N. and de Mello, C. P. (2007). A result on the total colouring of powers of cycles. Discrete Appl. Math., pages 585–597.
Chetwynd, A. G. and Hilton, A. J. W. (1988). Some refinements of the total chromatic number conjecture. Congr. Numer., pages 195–216.
Hamilton, G. M., Hilton, A. J. W., and Hind, H. R. F. (1999). Totally critical even order graphs. J. Comb. Theory Ser. B., pages 262–279.
Hilton, A. J. W. and Hind, H. R. (2002). Non-conformable subgraphs of non-conformable graphs. Discrete Math., pages 203–224.
Sánchez-Arroyo, A. (1989). Determining the total colouring number is NP-hard. Discrete Math., pages 315–319.
Vizing, V. G. (1968). Some unsolved problems in graph theory. Russ. Math. Surv., pages 125–141.
Yap, H. P. (1996). Total colourings of graphs. Springer.
Zorzi, A., Figueiredo, C., Machado, R., Zatesko, L., and Souza, U. (2021). Compositions, decompositions, and conformability for total coloring on power of cycle graphs. Discrete Appl. Math. https://doi.org/10.1016/j.dam.2021.06.012.
Published
2022-07-31
How to Cite
FARIA, Luerbio; NIGRO, Mauro; SASAKI, Diana.
The conformability of connected subcubic graphs. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 7. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 49-52.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2022.222744.
