On the conformable colorings of k-regular graphs - Faria, Luerbio; Nigro, Mauro; Sasaki, Diana (Anais do Encontro de Teoria da Computação (ETC); 2023: Anais do VIII Encontro de Teoria da Computação, 2023)
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 .