On the Complexity of Subfall Coloring of Graphs - Andrade, Davi de; Silva, Ana (Anais do Encontro de Teoria da Computação (ETC); 2021: Anais do VI Encontro de Teoria da Computação, 2021)
Given a graph G and a proper k-coloring f of G, a b-vertex in f is a vertex that is adjacent to every color class but its own. If every vertex is a b-vertex, then f is a fall k-coloring; and G has a subfall k-coloring if there is an induced H $\subseteq$ G such that H has a fall k-coloring. The subfall chromatic number of G is the largest positive integer $ψ_{fs}(G)$ such that G has a subfall $ψ_{fs}(G)$-coloring. We prove that deciding if a graph G has a subfall k-coloring is NP-complete for k $≥$ 4, and characterize graphs having a subfall 3-coloring. This answers a question posed by Dunbar et al. (2000) in their seminal paper. We also prove polinomiality for chordal graphs and cographs, and present a comparison with other known coloring metrics based on heuristics.