(Sub)Fall Coloring and B-Coloring Parameterized by Treewidth

• Davi de Andrade UFC
• Ana Silva UFC

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

Resumo

Given a proper coloring f of G, a vertex u is a b-vertex if it is adjacent to every color class distinct from its own. It is said to be a b-coloring if each color class contains at least one b-vertex, and a fall coloring if all vertices are b-vertices. Also, if f is a fall coloring of an induced subgraph H of G, then we say that f is a subfall coloring of G. In this paper, we provide algorithms for each of the decision problems related to these colorings whose running times are FPT when parameterized by the number of colors plus the treewidth of the input graph.

Palavras-chave: Computational Complexity, Graph Theory and Combinatorics

Referências

Andrade, D. and Silva, A. (2021). On the Complexity of Subfall Coloring of Graphs. In Anais do VI Encontro de Teoria da Computação, pages 70–73, Brasil. SBC.

Christen, C. A. and Selkow, S. M. (1979). Some Perfect Coloring Properties of Graphs.

Journal of Combinatorial Theory, Series B, 27(1):49–59.

Courcelle, B. (1990). The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs. Information and computation, 85(1):12–75.

Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms. Springer, 1st edition.

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 Combinatorial Computing, 33:257–273.

Garey, M. R., Johnson, D. S., and Stockmeyer, L. (1974). Some Simplified NP-Complete Problems. In STOC ’74, page 47–63. Association for Computing Machinery.

Harary, F. and Hedetniemi, S. (1970). The Achromatic Number of a Graph. Journal of Combinatorial Theory, 8(2):154–161.

Irving, R. W. and Manlove, D. F. (1999). The B-Chromatic Number of a Graph. Discrete Applied Mathematics, 91(1):127–141.

Jaffke, L., Lima, P. T., and Lokshtanov, D. (2021). B-Coloring Parameterized by CliqueWidth. In STACS 2021, volume 187 of LIPIcs, pages 43:1–43:15, Germany.

Kratochvíl, J., Tuza, Z., and Voigt, M. (2002). On the B-Chromatic Number of Graphs.

Journal of Optimization Theory and Applications, 109:310–320.

Panolan, F., Philip, G., and Saurabh, S. (2017). On the Parameterized Complexity of B-Chromatic Number. Journal of Computer and System Sciences, 84:120–131.

Telle, J. A. and Proskurowski, A. (1997). Algorithms for Vertex Partitioning Problems on Partial k-Trees. SIAM J. Discret. Math., 10:529–550.

Vatshelle, M. (2012). New Width Parameters of Graphs. PhD thesis, The University of Bergen.