Parameterized coloring problems on chordal graphs

DOI10.1016/J.TCS.2005.10.008zbMATH Open1087.68072OpenAlexW2106097003MaRDI QIDQ820152FDOQ820152

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

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

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)

Cites Work

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

Cited In (24)

• Title not available (Why is that?)
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets
• Data Reduction for Graph Coloring Problems
• A technique for exact computation of precoloring extension on interval graphs
• Incremental list coloring of graphs, parameterized by conservation
• 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
• Title not available (Why is that?)
• Parameterized and Exact Computation
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• Linear-Time Generation of Random Chordal Graphs
• Chordal deletion is fixed-parameter tractable
• Data reduction for graph coloring problems
• The χt-coloring problem
• A parameterized view on matroid optimization problems
• Open Problems on Graph Coloring for Special Graph Classes
• Mixing Color Coding-Related Techniques
• 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
• 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)