Parameterized complexity of vertex colouring
From MaRDI portal
Publication:1811065
DOI10.1016/S0166-218X(02)00242-1zbMATH Open1015.05027OpenAlexW2130673833MaRDI QIDQ1811065FDOQ1811065
Authors: Leizhen Cai 
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
Recommendations
- Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Vertex Coloring of Comparability+ke and –ke Graphs
- Data reduction for graph coloring problems
- Two complexity results for the vertex coloring problem
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Easy problems for tree-decomposable graphs
- Complexity of Finding Embeddings in a k-Tree
- Title not available (Why is that?)
- Title not available (Why is that?)
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Some simplified NP-complete graph problems
- The splittance of a graph
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Title not available (Why is that?)
- The NP-completeness column: an ongoing guide
- Generalized coloring for tree-like graphs
- Scheduling with incompatible jobs
- Title not available (Why is that?)
Cited In (55)
- Parameterized complexity of vertex splitting to pathwidth at most 1
- Finding optimal solutions with neighborly help
- Packing arc-disjoint cycles in oriented graphs
- Structural parameterizations of budgeted graph coloring
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Title not available (Why is that?)
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- Fine-grained parameterized complexity analysis of graph coloring problems
- Fixed-parameter tractability of \((n-k)\) list coloring
- Exact and parameterized algorithms for \((k,i)\)-coloring
- Sublinear approximation algorithms for boxicity and related problems
- Approximation and kernelization for chordal vertex deletion
- Parameterized complexity of optimizing list vertex-coloring through reconfiguration
- FPT and kernelization algorithms for the induced tree problem
- Complexity of stability
- Saving colors and max coloring: some fixed-parameter tractability results
- On structural parameterizations of graph motif and chromatic number
- Parameterized pre-coloring extension and list coloring problems
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Chordal editing is fixed-parameter tractable
- Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
- Role coloring bipartite graphs
- Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
- Fine-grained parameterized complexity analysis of graph coloring problems
- Vertex coloring of a graph for memory constrained scenarios
- Parameterized coloring problems on chordal graphs
- A survey of parameterized algorithms and the complexity of edge modification
- Parameterized complexity: the main ideas and connections to practical computing
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- The power of linear-time data reduction for maximum matching
- Open problems on graph coloring for special graph classes
- Chordal deletion is fixed-parameter tractable
- The vertex coloring problem and its generalizations
- Parameterized and exact algorithms for class domination coloring
- Parameterized and exact algorithms for class domination coloring
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Data reduction for graph coloring problems
- Data reduction for graph coloring problems
- The Power of Linear-Time Data Reduction for Maximum Matching
- Solving problems on graphs of high rank-width
- The parameterized complexity of cycle packing: indifference is not an issue
- Vertex Coloring of Comparability+ke and –ke Graphs
- List-coloring -- parameterizing from triviality
- Integer programming in parameterized complexity: five miniatures
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- On explaining integer vectors by few homogeneous segments
- Parameterized algorithms for conflict-free colorings of graphs
- Parameterized complexity of maximum edge colorable subgraph
- Solving problems on graphs of high rank-width
- Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization
- Saving colors and max coloring: some fixed-parameter tractability results
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- 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 complexity of vertex colouring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1811065)
