Top

Journal of Combinatorial Optimization

Published in:

19-10-2019

Tree-coloring problems of bounded treewidth graphs

Authors: Bi Li, Xin Zhang

Published in: Journal of Combinatorial Optimization | Issue 1/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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 \ge 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.

previous article Remarks on Barnette’s conjecture

next article The structure of graphs with given number of blocks and the maximum Wiener index

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Bodlaender HL (1998) A partial k-arboretum of graphs with bounded treewidth. Theor Comput Sci 209(1–2):1–45MathSciNetCrossRef

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

Bodlaender HL, Fomin FV (2005) Equitable colorings of bounded treewidth graphs. Theor Comput Sci 349(1):22–30MathSciNetCrossRef

Chartrand G, Kronk HV (1969) The point-arboricity of planar graphs. J Lond Math Soc 1:612–616MathSciNetCrossRef

Chen G, Gao Y, Shan S, Wang G, Wu J (2017) Equitable vertex arboricity of 5-degenerate graphs. J Comb Optim 34(2):426–432MathSciNetCrossRef

Downey RG, Thilikos DM (2011) Confronting intractability via parameters. Comput Sci Rev 5(4):279–317CrossRef

Esperet L, Lemoine L, Fre M (2015) Equitable partition of graphs into induced forests. Discrete Math 338(8):1481–1493MathSciNetCrossRef

Fellows MR, Fomin FV, Lokshtanov D, Rosamond F, Saurabh S, Szeider S, Thomassen C (2011) On the complexity of some colorful problems parameterized by treewidth. Inf Comput 209(2):143–153MathSciNetCrossRef

Fiala J, Golovach PA, Kratochvíl J (2011) Parameterized complexity of coloring problems: treewidth versus vertex cover. Theor Comput Sci 412(23):2513–2523MathSciNetCrossRef

Furmanczyk H (2006) Equitable coloring of graph products. Opusc Math 26(1):31–44MathSciNet

Grünbaum B (1973) Acyclic colorings of planar graphs. Israel J Math 14(4):390–408MathSciNetCrossRef

Kostochka AV, Nakprasit K, Pemmaraju SV (2005) On equitable coloring of \(d\)-degenerate graphs. SIAM J Discrete Math 19(1):83–95MathSciNetCrossRef

Kronk H, Mitchem J (1975) Critical point-arboritic graphs. J Lond Math Soc 2–9(3):459–466MathSciNetCrossRef

Kubale M (1989) Interval vertex-coloring of a graph with forbidden colors. Discrete Math 74(1):125–136 (Special double issue)MathSciNetMATH

Nakprasit KM, Nakprasit K (2016) Complexity of equitable tree-coloring problems. ArXiv e-prints

Meyer W (1973) Equitable coloring. Am Math Mon 80(8):920–922MathSciNetCrossRef

Robertson N, Seymour PD (1986) Graph minors. II. Algorithmic aspects of tree-width. J Algorithms 7(3):309–322MathSciNetCrossRef

Wu J-L, Zhang X, Li H (2013) Equitable vertex arboricity of graphs. Discrete Math 313(23):2696–2701MathSciNetCrossRef

Title: Tree-coloring problems of bounded treewidth graphs
Authors: Bi Li
Xin Zhang
Publication date: 19-10-2019
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2020
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-019-00461-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2020

Neighbor sum distinguishing total colorings of IC-planar graphs with maximum degree 13

Neighbor-distinguishing total coloring of planar graphs with maximum degree twelve

On the König deficiency of zero-reducible graphs

Neighbor product distinguishing total colorings of 2-degenerate graphs

Remarks on Barnette’s conjecture

Approximation algorithms for two-stage flexible flow shop scheduling

Premium Partner