Parameterized coloring problems on chordal graphs

DOI10.1016/J.TCS.2005.10.008MaRDI QIDQ820152zbMATH OpenOpenAlexFDO

Authors 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

interval graphschordal graphsparameterized complexitycoloringprecoloring extension

Mathematics Subject Classification ID

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

Recommendations

• Parameterized and Exact Computation
• Precoloring extension on chordal graphs
• scientific article; zbMATH DE number 772747
• scientific article; zbMATH DE number 772760
• Precoloring Extension III: Classes of Perfect Graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 5604125 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 772760 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Algorithmic Aspects of Vertex Elimination on Graphs
• Edge coloring nearly bipartite graphs
• Finding and counting given length cycles
• Finding odd cycle transversals.
• Fixed-parameter tractability of graph modification problems for hereditary properties
• On generalized graphs
• Parameterized and Exact Computation
• Parameterized complexity of vertex colouring
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• Precoloring Extension III: Classes of Perfect Graphs
• Precoloring extension on unit interval graphs
• Precoloring extension. I: Interval graphs
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Treewidth. Computations and approximations

Cited in

(25)

• Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• scientific article; zbMATH DE number 7651188 (Why is no real title available?)
• Incremental list coloring of graphs, parameterized by conservation
• A technique for exact computation of precoloring extension on interval graphs
• Fixed-parameter tractable distances to sparse graph classes
• Chordal editing is fixed-parameter tractable
• Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
• The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation
• scientific article; zbMATH DE number 7525474 (Why is no real title available?)
• Parameterized and Exact Computation
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• Chordal deletion is fixed-parameter tractable
• Open problems on graph coloring for special graph classes
• Data reduction for graph coloring problems
• Data reduction for graph coloring problems
• A parameterized view on matroid optimization problems
• The χt-coloring problem
• Precoloring extension on chordal graphs
• Mixing Color Coding-Related Techniques
• Deterministic algorithms for matching and packing problems based on representative sets
• Linear-time generation of random chordal graphs
• Representative families: a unified tradeoff-based approach
• Coloring chip configurations on graphs and digraphs
• Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820152)