Generalized coloring for tree-like graphs

DOI10.1016/S0166-218X(96)00085-6zbMath0879.68076OpenAlexW2088330156MaRDI QIDQ1363645

Petra Scheffler, Klaus Jansen

Publication date: 10 August 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

list coloringprecoloring extension

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (44)

Coloring problems on bipartite graphs of small diameter ⋮ The \(d\)-precoloring problem for \(k\)-degenerate graphs ⋮ Complexity of list coloring problems with a fixed total number of colors ⋮ List coloring in the absence of two subgraphs ⋮ The parameterised complexity of list problems on graphs of bounded treewidth ⋮ Answering conjunctive queries with inequalities ⋮ Time slot scheduling of compatible jobs ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ Data reduction for graph coloring problems ⋮ Clique‐width: Harnessing the power of atoms ⋮ Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees ⋮ Combinatorial problems on \(H\)-graphs ⋮ On the complexity of coloring ‐graphs ⋮ On the complexity of some colorful problems parameterized by treewidth ⋮ List homomorphism: beyond the known boundaries ⋮ Consensus models: computational complexity aspects in modern approaches to the list coloring problem ⋮ Acyclic and star colorings of cographs ⋮ Coloring graphs without short cycles and long induced paths ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ On the parameterized complexity of coloring graphs in the absence of a linear forest ⋮ Bandwidth consecutive multicolorings of graphs ⋮ On coloring problems with local constraints ⋮ On coloring problems with local constraints ⋮ Using Local Search to Speed Up Filtering Algorithms for Some NP-Hard Constraints ⋮ Exploring the complexity boundary between coloring and list-coloring ⋮ Exploring the complexity boundary between coloring and list-coloring ⋮ Closing complexity gaps for coloring problems on \(H\)-free graphs ⋮ Using local search to speed up filtering algorithms for some NP-hard constraints ⋮ Slightly Superexponential Parameterized Problems ⋮ List total colorings of series-parallel graphs ⋮ A note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model ⋮ Hard coloring problems in low degree planar bipartite graphs ⋮ On \(H\)-topological intersection graphs ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Parameterized complexity of vertex colouring ⋮ On list \(k\)-coloring convex bipartite graphs ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs ⋮ List Coloring in the Absence of a Linear Forest ⋮ Weighted coloring: further complexity and approximability results ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure ⋮ All subgraphs of a wheel are 5-coupled-choosable ⋮ On algorithms for (\(P_5\), gem)-free graphs

Cites Work

• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Complement reducible graphs
• Precoloring extension. I: Interval graphs
• A Linear Recognition Algorithm for Cographs
• Graph minors. II. Algorithmic aspects of tree-width
• Linear-time computation of optimal subgraphs of decomposable graphs
• A linear time algorithm for finding tree-decompositions of small treewidth
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Generalized coloring for tree-like graphs