Parameterized complexity of coloring problems: treewidth versus vertex cover
From MaRDI portal
Publication:534566
DOI10.1016/j.tcs.2010.10.043zbMath1216.68127OpenAlexW2103715966MaRDI QIDQ534566
Petr A. Golovach, Jiří Fiala, Jan Kratochvíl
Publication date: 18 May 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.10.043
Related Items
Iterated Type Partitions ⋮ Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics ⋮ Computing L(p,1)-Labeling with Combined Parameters ⋮ An analysis of the parameterized complexity of periodic timetabling ⋮ Parameterized complexity of distance labeling and uniform channel assignment problems ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Data reduction for graph coloring problems ⋮ Problems hard for treewidth but easy for stable gonality ⋮ Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees ⋮ Colouring a dominating set without conflicts: \(q\)-subset square colouring ⋮ Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization ⋮ Parameterized complexity for iterated type partitions and modular-width ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Extended MSO model checking via small vertex integrity ⋮ Unnamed Item ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Exact and Parameterized Algorithms for (k, i)-Coloring ⋮ Complexity of conflict-free colorings of graphs ⋮ On directed covering and domination problems ⋮ Computing \(L(p, 1)\)-labeling with combined parameters ⋮ Parameterizing by the number of numbers ⋮ Optimal data reduction for graph coloring using low-degree polynomials ⋮ Finding vertex-surjective graph homomorphisms ⋮ Tree-coloring problems of bounded treewidth graphs ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Structural parameterizations of budgeted graph coloring ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Structural parameterizations of budgeted graph coloring ⋮ Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ On bounded-degree vertex deletion parameterized by treewidth ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials ⋮ Parameterized complexity of list coloring and max coloring ⋮ On Directed Covering and Domination Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Non-standard approaches to integer programming
- Equitable colorings of bounded treewidth graphs
- An application of simultaneous diophantine approximation in combinatorial optimization
- Channel assignment on graphs of bounded treewidth
- Coloring squares of planar graphs with girth six
- A survey on labeling graphs with a condition at distance two
- Systems of pairs of \(q\)-distant representatives, and graph colorings
- Integer Programming with a Fixed Number of Variables
- Capacitated Domination and Covering: A Parameterized Perspective
- Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
- Treewidth: Characterizations, Applications, and Computations
- Graph Layout Problems Parameterized by Vertex Cover
- On the Complexity of Some Colorful Problems Parameterized by Treewidth
- List-Coloring Squares of Sparse Subcubic Graphs
- Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
- A Linear Time Algorithm for L(2,1)-Labeling of Trees
- Minkowski's Convex Body Theorem and Integer Programming
- Two-Processor Scheduling with Start-Times and Deadlines
- Nondeterminism within $P^ * $
- Graph colorings with local constraints -- a survey
- Coloring Powers of Planar Graphs
- The $L(2,1)$-Labeling Problem on Graphs
- Automata, Languages and Programming
This page was built for publication: Parameterized complexity of coloring problems: treewidth versus vertex cover
