On the Complexity of Subfall Coloring of Graphs

• Davi de Andrade UFC
• Ana Silva UFC https://orcid.org/0000-0001-8917-0564

DOI: https://doi.org/10.5753/etc.2021.16383

Resumo

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.

Palavras-chave: Fall Coloring, Subfall Coloring, Graph Coloring, Subfall Continuity, Computational Complexity

Referências

Araujo, J. and Linhares Sales, C. (2012). On the Grundy number of graphs with fewP4’s. Discrete Applied Mathematics, 160(18):2514–2522.

Bonomo, F., Duran, G., Maffray, F., Marenco, J., and Valencia-Pabon, M. (2009). On the b-Coloring of Cographs and P4-Sparse Graphs. Graphs and Combinatorics, 25:153–167.

Chudnovsky, M., Scott, A., Seymour, P., and Spirkl, S. (2020). Detecting an Odd Hole. J. ACM, 67(1).

Dailey, D. P. (1980). Uniqueness of colorability and colorability of planar 4-regular graphs are -complete. Discrete Mathematics, 30(3):289–293.

Descartes, B. (1954). Solution to advanced problem no. 4526.Amer. Math. Monthly,61:352.

Dunbar, J., Hedetniemi, S., Hedetniemi, S., Jacobs, D., Knisely, J., Laskar, R., and Rall,D. (2000). Fall Colorings of Graphs.J. of Combinatorial Mathematics and Combina-torial Computing, 33:257–273.

Havet, F., Linhares Sales, C., and Sampaio, L. (2012). b-coloring of tight graphs.DiscreteApplied Mathematics, 160(18):2709–2715.

Havet, F. and Rocha, L. (2013). On the Grundy and b-Chromatic Numbers of a Graph.Algorithmica, 65:885–899.

Irving, R. W. and Manlove, D. F. (1999). The b-chromatic number of a graph.DiscreteApplied Mathematics, 91(1):127–141.

Lauri, J. and Mitillos, C. (2019). Complexity of Fall Coloring for Restricted GraphClasses. 11638:352–364.

Sampaio, L. (2012).Algorithmic aspects of graph colourings heuristics. PhD thesis,Université Nice Sophia Antipolis.

Silva, A. (2019). Graphs with small fall-spectrum.Discrete Applied Mathematics,254:183–188.