Open AccessOn the Complexity of Subfall Coloring of Graphs
Author(s) -
Davi de Andrade,
Ana Silva
Publication year - 2021
Language(s) - English
Resource type - Conference proceedings
DOI - 10.5753/etc.2021.16383
Subject(s) - combinatorics , complete coloring , fractional coloring , greedy coloring , brooks' theorem , mathematics , graph coloring , vertex (graph theory) , chordal graph , edge coloring , list coloring , graph , discrete mathematics , graph power , 1 planar graph , line graph
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 $\psi_{fs}(G)$ such that G has a subfall $\psi_{fs}(G)$-coloring. We prove that deciding if a graph G has a subfall k-coloring is NP-complete for k $\geq$ 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.