Parameterized complexity of vertex colouring
From MaRDI portal
Publication:1811065
DOI10.1016/S0166-218X(02)00242-1zbMath1015.05027OpenAlexW2130673833MaRDI QIDQ1811065
Publication date: 10 June 2003
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00242-1
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (46)
Parameterized coloring problems on chordal graphs ⋮ Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems ⋮ Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ Chordal editing is fixed-parameter tractable ⋮ Solving Problems on Graphs of High Rank-Width ⋮ Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ Parameterized and exact algorithms for class domination coloring ⋮ List-coloring -- parameterizing from triviality ⋮ Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Data reduction for graph coloring problems ⋮ Integer programming in parameterized complexity: five miniatures ⋮ Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization ⋮ Sublinear approximation algorithms for boxicity and related problems ⋮ Packing arc-disjoint cycles in oriented graphs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ FPT and kernelization algorithms for the induced tree problem ⋮ Parameterized and Exact Algorithms for Class Domination Coloring ⋮ On Structural Parameterizations of Graph Motif and Chromatic Number ⋮ Exact and Parameterized Algorithms for (k, i)-Coloring ⋮ Solving problems on graphs of high rank-width ⋮ The power of linear-time data reduction for maximum matching ⋮ Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs ⋮ Saving colors and max coloring: some fixed-parameter tractability results ⋮ Closing complexity gaps for coloring problems on \(H\)-free graphs ⋮ On explaining integer vectors by few homogeneous segments ⋮ Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs ⋮ Chordal deletion is fixed-parameter tractable ⋮ Temporal graph classes: a view through temporal separators ⋮ Efficient algorithms for measuring the funnel-likeness of DAGs ⋮ Parameterized algorithms for conflict-free colorings of graphs ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Fixed-parameter tractability of \((n-k)\) list coloring ⋮ The parameterized complexity of cycle packing: indifference is not an issue ⋮ Data Reduction for Graph Coloring Problems ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Polynomial kernels for vertex cover parameterized by small degree modulators ⋮ Parameterized Complexity ⋮ Role coloring bipartite graphs ⋮ The Power of Linear-Time Data Reduction for Maximum Matching ⋮ Parameterized Pre-Coloring Extension and List Coloring Problems ⋮ Fine-grained parameterized complexity analysis of graph coloring problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- The splittance of a graph
- Some simplified NP-complete graph problems
- Scheduling with incompatible jobs
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Generalized coloring for tree-like graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Easy problems for tree-decomposable graphs
- The NP-completeness column: an ongoing guide
- Complexity of Finding Embeddings in a k-Tree
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: Parameterized complexity of vertex colouring
