Parameterized complexity of vertex colouring
From MaRDI portal
(Redirected from Publication:1811065)
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)
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
Cites work
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3632548 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1095172 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 854567 (Why is no real title available?)
- scientific article; zbMATH DE number 1409207 (Why is no real title available?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Complexity of Finding Embeddings in a k-Tree
- Easy problems for tree-decomposable graphs
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Generalized coloring for tree-like graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Scheduling with incompatible jobs
- Some simplified NP-complete graph problems
- The NP-completeness column: an ongoing guide
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The splittance of a graph
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
Cited in
(55)- Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
- Packing arc-disjoint cycles in oriented graphs
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Structural parameterizations of budgeted graph coloring
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- 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
- Chordal editing is fixed-parameter tractable
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Parameterized pre-coloring extension and list coloring problems
- 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
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Parameterized complexity: the main ideas and connections to practical computing
- The power of linear-time data reduction for maximum matching
- A survey of parameterized algorithms and the complexity of edge modification
- Chordal deletion is fixed-parameter tractable
- The vertex coloring problem and its generalizations
- Open problems on graph coloring for special graph classes
- Parameterized and exact algorithms for class domination coloring
- Parameterized and exact algorithms for class domination coloring
- Data reduction for graph coloring problems
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Data reduction for graph coloring problems
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- 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
- Parameterized complexity of vertex splitting to pathwidth at most 1
- List-coloring -- parameterizing from triviality
- Vertex Coloring of Comparability+ke and –ke Graphs
- 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
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization
- Saving colors and max coloring: some fixed-parameter tractability results
- Finding optimal solutions with neighborly help
- 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)
