Parameterized coloring problems on chordal graphs

DOI10.1016/j.tcs.2005.10.008zbMath1087.68072OpenAlexW2106097003MaRDI QIDQ820152

Dániel Marx

Publication date: 6 April 2006

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.10.008

zbMATH Keywords

chordal graphscoloringinterval graphsparameterized complexityprecoloring extension

Mathematics Subject Classification ID

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

Related Items (21)

Linear-Time Generation of Random Chordal Graphs ⋮ Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ Chordal editing is fixed-parameter tractable ⋮ Mixing Color Coding-Related Techniques ⋮ Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets ⋮ Fixed-parameter tractable distances to sparse graph classes ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ Data reduction for graph coloring problems ⋮ Representative families: a unified tradeoff-based approach ⋮ Unnamed Item ⋮ Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs ⋮ Closing complexity gaps for coloring problems on \(H\)-free graphs ⋮ Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs ⋮ Chordal deletion is fixed-parameter tractable ⋮ Unnamed Item ⋮ The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ Data Reduction for Graph Coloring Problems ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ A parameterized view on matroid optimization problems ⋮ A TECHNIQUE FOR EXACT COMPUTATION OF PRECOLORING EXTENSION ON INTERVAL GRAPHS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding and counting given length cycles
• Finding odd cycle transversals.
• Precoloring extension. I: Interval graphs
• Edge coloring nearly bipartite graphs
• Treewidth. Computations and approximations
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Parameterized complexity of vertex colouring
• Precoloring extension on unit interval graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Precoloring Extension III: Classes of Perfect Graphs
• Parameterized and Exact Computation
• On generalized graphs
• Algorithms - ESA 2003

This page was built for publication: Parameterized coloring problems on chordal graphs