Data reduction for graph coloring problems
From MaRDI portal
Publication:393081
DOI10.1016/j.ic.2013.08.005zbMath1435.68124OpenAlexW1779781738MaRDI QIDQ393081
Stefan Kratsch, Bart M. P. Jansen
Publication date: 16 January 2014
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2013.08.005
Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies, Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems, Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results, A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion, Sparsification upper and lower bounds for graph problems and not-all-equal SAT, Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization, Dominator coloring and CD coloring in almost cluster graphs, Unnamed Item, Exact and Parameterized Algorithms for (k, i)-Coloring, Saving colors and max coloring: some fixed-parameter tractability results, Optimal data reduction for graph coloring using low-degree polynomials, Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Fixed-parameter tractability of \((n-k)\) list coloring, Parameterized Complexity of Conflict-Free Graph Coloring, Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs, FPT is characterized by useful obstruction sets, Revisiting connected vertex cover: FPT algorithms and lossy kernels, Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials, Computing the chromatic number using graph decompositions via matrix rank, Structural parameterizations of Tracking Paths problem, Fine-grained parameterized complexity analysis of graph coloring problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Infeasibility of instance compression and succinct PCPs for NP
- On the complexity of some colorful problems parameterized by treewidth
- The complexity ecology of parameters: An illustration using bounded max leaf number
- Some consequences of non-uniform conditions on uniform classes
- Parameterized coloring problems on chordal graphs
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- On problems without polynomial kernels
- Axioms and hulls
- Scheduling with incompatible jobs
- Generalized coloring for tree-like graphs
- Parameterized complexity of vertex colouring
- Edge dominating set and colorings on graphs with fixed clique-width
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Intractability of Clique-Width Parameterizations
- A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
- Kernelization: New Upper and Lower Bound Techniques
- Graph colorings with local constraints -- a survey
- Graph Classes: A Survey
- Graph-Theoretic Concepts in Computer Science
