TY - JOUR
AU - Faria, Luerbio
AU - Nigro, Mauro
AU - Sasaki, Diana
PY - 2023/08/06
TI - On the conformable colorings of k-regular graphs
JF - Anais do Encontro de Teoria da Computação (ETC); 2023: Anais do VIII Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2023.230063
KW -
N2 - 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 (∆− d G (v)). The only connected subcubic not anticonformable graph is the triangular prism graph L 3 . 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 H k , where H 3 = L 3 .
UR - https://sol.sbc.org.br/index.php/etc/article/view/24735