Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees

DOI10.1016/j.tcs.2019.02.029zbMath1423.68201arXiv1709.05000OpenAlexW2963710853MaRDI QIDQ2420639

Cédric Bentz

Publication date: 6 June 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1709.05000

zbMATH Keywords

dynamic programmingNP-completenesscographssplit graphstree-widthmaximum flowslocally bounded list-colorings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Thinness of product graphs ⋮ On \(d\)-stable locally checkable problems parameterized by mim-width

Cites Work

• Unnamed Item
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
• Restrictions of graph partition problems. I
• Bounded vertex colorings of graphs
• Equitable colorings of bounded treewidth graphs
• On the complexity of a restricted list-coloring problem
• Treewidth. Computations and approximations
• Complexity of list coloring problems with a fixed total number of colors
• Generalized coloring for tree-like graphs
• Mutual exclusion scheduling
• Bin packing with fixed number of bins revisited
• On the thinness and proper thinness of a graph
• Locally boundedk-colorings of trees
• The NP-Completeness of Edge-Coloring
• Graph Classes: A Survey

This page was built for publication: Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees