On the conformable colorings of k-regular graphs
Resumo
In 1988, Chetwynd and Hilton defined conformable vertex colorings when trying to characterize the vertex colorings induced by a (∆ + 1)-total coloring. Anticonformable colorings were used to characterize the subcubic conformable graphs. A graph G is anticonformable if it has a (∆ + 1)-vertex coloring such that the number of color classes (including empty color classes) with the same parity as |V| is at most def(G) = ∑v∈V (∆− dG(v)). The only connected subcubic not anticonformable graph is the triangular prism graph L3. In this paper, we prove that if k is even, then every k-regular graph is not anticonformable; and if k ≥ 3 is odd, then there is a not anticonformable graph Hk, where H3 = L3.
Referências
Behzad, M. (1965). Graphs 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.
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., 256(1):203–224.
Nigro, M., Adauto, M. N., and Sasaki, D. (2021). On total coloring of 4-regular circulant graphs. Procedia Computer Science, 195:315–324.
Nigro, M., Faria, L., and Sasaki, D. (2022a). A conformabilidade dos grafos subcúbicos. In Anais do LIV Simpósio Brasileiro de Pesquisa Operacional. Galoá.
Nigro, M., Faria, L., and Sasaki, D. (2022b). A conformabilidade dos grafos subcúbicos conexos. In Anais do VII Encontro de Teoria da Computação, pages 49–52.
Vizing, V. (1964). On an estimate of the chromatic class of a p-graph. Metody Diskret. Analiz., 3: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.
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.
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., 256(1):203–224.
Nigro, M., Adauto, M. N., and Sasaki, D. (2021). On total coloring of 4-regular circulant graphs. Procedia Computer Science, 195:315–324.
Nigro, M., Faria, L., and Sasaki, D. (2022a). A conformabilidade dos grafos subcúbicos. In Anais do LIV Simpósio Brasileiro de Pesquisa Operacional. Galoá.
Nigro, M., Faria, L., and Sasaki, D. (2022b). A conformabilidade dos grafos subcúbicos conexos. In Anais do VII Encontro de Teoria da Computação, pages 49–52.
Vizing, V. (1964). On an estimate of the chromatic class of a p-graph. Metody Diskret. Analiz., 3: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.
Publicado
06/08/2023
Como Citar
FARIA, Luerbio; NIGRO, Mauro; SASAKI, Diana.
On the conformable colorings of k-regular graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 25-29.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.230063.
