(Star, k)-colourings of graphs with bounded treewidth

• C. A. Weffort-Santos UNICAMP http://orcid.org/0000-0001-6691-5316
• L. L. C. Pedrosa UNICAMP http://orcid.org/0000-0003-1001-082X

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

Resumo

We study a generalization of graph colouring define as follows. Given a graph G, a (star, k)-colouring of G is a colouring c : V(G) → {1, ..., k} such that every colour class induces a star. We propose an O*(2^(O(tw))k^(tw)-time algorithm that decides whether a graph G of treewidth at most tw admits a (star, k)-colouring. This resolves an open problem posed by Angelini et al. in 2017. Our approach can be extended to other defective colouring models.

Palavras-chave: defective colouring, star colouring, parameterized algorithms

Referências

Alon, N., Ding, G. , Oporowski, B. and Vertigan, D. Partitioning into graphs with only small components. Journal of Combinatorial Theory, Series B, 87(2):231--243, Mar. 2003.

Angelini, P., Bekos, M. A., De Luca, F., Didimo, W., Kaufmann, M., Kobourov, S., Montecchiani, F., Raftopoulou, C. N., Roselli, V. and Symvonis, A. Vertex-coloring with defects. JGAA, 21(3):313-340, 2017.

Courcelle, B. The monadic second-order logic of graphs III: Tree-decompositions, minors and complexity issues. RAIRO-Theor. Inf. Appl., 26(3):257--286, 1992.

Cowen, L., Cowen, R., and Woodall, D.. Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency. J. Graph Theory, 10(2):187-195, 1986.

Cowen, L., Goddard, W. and Jesurum, C. Coloring with defect. In Proc. of SODA, pages 548--557, 1997.

Dorbec, P., Montassier, M. and Ochem, P. Vertex partitions of graphs into cographs and stars. J. Graph Theory, 75(1):75--90, Feb, 2013.

Edelman, A., Hassidim, A., Nguyen, H. and Onak, K. An efficient partitioning oracle for bounded treewidth graphs. In Proc. of APPROX, pages 530-451, 2011.

Wood, D. R. Defective and clustered graph colouring. Electronic J. Combin., 1000:1--71, Apr, 2018.