nach oben

Journal of Combinatorial Optimization

Erschienen in:

19.10.2019

Tree-coloring problems of bounded treewidth graphs

verfasst von: Bi Li, Xin Zhang

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Remarks on Barnette’s conjecture

Nächster Artikel The structure of graphs with given number of blocks and the maximum Wiener index

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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

Titel: Tree-coloring problems of bounded treewidth graphs
verfasst von: Bi Li
Xin Zhang
Publikationsdatum: 19.10.2019
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 1/2020
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-019-00461-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2020

On the König deficiency of zero-reducible graphs

Bounds on upper transversals in hypergraphs

Graphs with equal domination and covering numbers

On the extremal graphs with respect to the total reciprocal edge-eccentricity

Neighbor product distinguishing total colorings of 2-degenerate graphs

Less is more approach for competing groups scheduling with different learning effects