×

Tree-coloring problems of bounded treewidth graphs. (English) Zbl 1434.05055

Summary: This paper studies the parameterized complexity of the tree-coloring problem and equitable tree-coloring problem. Given a graph \(G=(V,E)\) and an integer \(r\geq 1\), we give an FPT algorithm to decide whether there is a tree-\(r\)-coloring of graph \(G\) when parameterized by treewidth. Moreover, we prove that to decide the existence of an equitable tree-\(r\)-coloring of graph \(G\) is W[1]-hard when parameterized by treewidth; and that it is polynomial solvable in the class of graphs with bounded treewidth.

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bodlaender, Hl, A partial k-arboretum of graphs with bounded treewidth, Theor Comput Sci, 209, 1-2, 1-45 (1998) · Zbl 0912.68148 · doi:10.1016/S0304-3975(97)00228-4
[2] Bodlaender HL, Drange P, Dregi M, Fomin F, Lokshtanov D, Pilipczuk M (2013) An \(o(c^k n) 5\)-approximation algorithm for treewidth. In: 2013 IEEE 54th annual symposium on foundations of computer science (FOCS), pp 499-508 · Zbl 1333.05282
[3] Bodlaender, Hl; Fomin, Fv, Equitable colorings of bounded treewidth graphs, Theor Comput Sci, 349, 1, 22-30 (2005) · Zbl 1086.68096 · doi:10.1016/j.tcs.2005.09.027
[4] Chartrand, G.; Kronk, Hv, The point-arboricity of planar graphs, J Lond Math Soc, 1, 612-616 (1969) · Zbl 0175.50505 · doi:10.1112/jlms/s1-44.1.612
[5] Chen, G.; Gao, Y.; Shan, S.; Wang, G.; Wu, J., Equitable vertex arboricity of 5-degenerate graphs, J Comb Optim, 34, 2, 426-432 (2017) · Zbl 1376.05051 · doi:10.1007/s10878-016-9997-8
[6] Downey, Rg; Thilikos, Dm, Confronting intractability via parameters, Comput Sci Rev, 5, 4, 279-317 (2011) · Zbl 1298.68094 · doi:10.1016/j.cosrev.2011.09.002
[7] Esperet, L.; Lemoine, L.; Fre, M., Equitable partition of graphs into induced forests, Discrete Math, 338, 8, 1481-1493 (2015) · Zbl 1310.05169 · doi:10.1016/j.disc.2015.03.019
[8] Fellows, Mr; Fomin, Fv; Lokshtanov, D.; Rosamond, F.; Saurabh, S.; Szeider, S.; Thomassen, C., On the complexity of some colorful problems parameterized by treewidth, Inf Comput, 209, 2, 143-153 (2011) · Zbl 1223.05070 · doi:10.1016/j.ic.2010.11.026
[9] Fiala, J.; Golovach, Pa; Kratochvíl, J., Parameterized complexity of coloring problems: treewidth versus vertex cover, Theor Comput Sci, 412, 23, 2513-2523 (2011) · Zbl 1216.68127 · doi:10.1016/j.tcs.2010.10.043
[10] Furmanczyk, H., Equitable coloring of graph products, Opusc Math, 26, 1, 31-44 (2006) · Zbl 1142.05025
[11] Grünbaum, B., Acyclic colorings of planar graphs, Israel J Math, 14, 4, 390-408 (1973) · Zbl 0265.05103 · doi:10.1007/BF02764716
[12] Kostochka, Av; Nakprasit, K.; Pemmaraju, Sv, On equitable coloring of \(d\)-degenerate graphs, SIAM J Discrete Math, 19, 1, 83-95 (2005) · Zbl 1082.05037 · doi:10.1137/S0895480103436505
[13] Kronk, H.; Mitchem, J., Critical point-arboritic graphs, J Lond Math Soc, 2-9, 3, 459-466 (1975) · Zbl 0298.05132 · doi:10.1112/jlms/s2-9.3.459
[14] Kubale, M., Interval vertex-coloring of a graph with forbidden colors, Discrete Math, 74, 1, 125-136 (1989) · Zbl 0682.05033
[15] Nakprasit KM, Nakprasit K (2016) Complexity of equitable tree-coloring problems. ArXiv e-prints · Zbl 1253.05072
[16] Meyer, W., Equitable coloring, Am Math Mon, 80, 8, 920-922 (1973) · Zbl 0279.05106 · doi:10.1080/00029890.1973.11993408
[17] Robertson, N.; Seymour, Pd, Graph minors. II. Algorithmic aspects of tree-width, J Algorithms, 7, 3, 309-322 (1986) · Zbl 0611.05017 · doi:10.1016/0196-6774(86)90023-4
[18] Wu, J-L; Zhang, X.; Li, H., Equitable vertex arboricity of graphs, Discrete Math, 313, 23, 2696-2701 (2013) · Zbl 1280.05047 · doi:10.1016/j.disc.2013.08.006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.