Parameterized complexity of coloring problems: treewidth versus vertex cover
From MaRDI portal
Publication:534566
DOI10.1016/J.TCS.2010.10.043zbMATH Open1216.68127OpenAlexW2103715966MaRDI QIDQ534566FDOQ534566
Authors: Jiří Fiala, Petr A. Golovach, 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
Recommendations
- Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
- On the Complexity of Some Colorful Problems Parameterized by Treewidth
- On the complexity of some colorful problems parameterized by treewidth
- The parameterised complexity of list problems on graphs of bounded treewidth
- Parameterized complexity of vertex colouring
Cites Work
- Integer Programming with a Fixed Number of Variables
- Minkowski's Convex Body Theorem and Integer Programming
- Graph colorings with local constraints -- a survey
- Title not available (Why is that?)
- A survey on labeling graphs with a condition at distance two
- Two-Processor Scheduling with Start-Times and Deadlines
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- An application of simultaneous diophantine approximation in combinatorial optimization
- Title not available (Why is that?)
- Nondeterminism within $P^ * $
- Coloring squares of planar graphs with girth six
- Graph Layout Problems Parameterized by Vertex Cover
- The $L(2,1)$-Labeling Problem on Graphs
- Treewidth: Characterizations, Applications, and Computations
- Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
- Capacitated Domination and Covering: A Parameterized Perspective
- A Linear Time Algorithm for L(2,1)-Labeling of Trees
- Automata, Languages and Programming
- List-Coloring Squares of Sparse Subcubic Graphs
- Coloring Powers of Planar Graphs
- Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
- Systems of pairs of \(q\)-distant representatives, and graph colorings
- Channel assignment on graphs of bounded treewidth
- On the Complexity of Some Colorful Problems Parameterized by Treewidth
- Non-standard approaches to integer programming
- Equitable colorings of bounded treewidth graphs
Cited In (45)
- Structural parameterizations of budgeted graph coloring
- Fixed-parameter tractability of \((n-k)\) list coloring
- Structural parameterizations of budgeted graph coloring
- Grundy Distinguishes Treewidth from Pathwidth
- Fixed-parameter tractability of \((n-k)\) list coloring
- Optimal data reduction for graph coloring using low-degree polynomials
- Exact and parameterized algorithms for \((k,i)\)-coloring
- On directed covering and domination problems
- Incremental list coloring of graphs, parameterized by conservation
- On directed covering and domination problems
- Optimal data reduction for graph coloring using low-degree polynomials
- Algorithmic applications of tree-cut width
- Computing \(L(p, 1)\)-labeling with combined parameters
- Finding vertex-surjective graph homomorphisms
- Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
- Fine-grained parameterized complexity analysis of graph coloring problems
- On bounded-degree vertex deletion parameterized by treewidth
- Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees
- An analysis of the parameterized complexity of periodic timetabling
- Extended MSO model checking via small vertex integrity
- Open problems on graph coloring for special graph classes
- Data reduction for graph coloring problems
- Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems
- Colouring a dominating set without conflicts: \(q\)-subset square colouring
- Problems hard for treewidth but easy for stable gonality
- Grundy distinguishes treewidth from pathwidth
- The parameterized complexity of maximum betweenness centrality
- Parameterized complexity of vertex colouring
- Iterated Type Partitions
- Aspects of the complexity of \((\gamma,\mu)\)-coloring
- Computing L(p,1)-Labeling with Combined Parameters
- On the complexity of some colorful problems parameterized by treewidth
- Complexity of conflict-free colorings of graphs
- Title not available (Why is that?)
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Parameterized complexity of list coloring and max coloring
- Title not available (Why is that?)
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization
- Resolving conflicts for lower-bounded clustering
- Parameterized complexity of distance labeling and uniform channel assignment problems
- Combinatorial \(n\)-fold integer programming and applications
- Tree-coloring problems of bounded treewidth graphs
- Parameterized complexity for iterated type partitions and modular-width
This page was built for publication: Parameterized complexity of coloring problems: treewidth versus vertex cover
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q534566)
