Computing the chromatic number using graph decompositions via matrix rank

DOI10.1016/j.tcs.2019.08.006zbMath1431.68053OpenAlexW2966702489WikidataQ127398272 ScholiaQ127398272MaRDI QIDQ2330132

Bart M. P. Jansen, Jesper Nederlof

Publication date: 18 October 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9510/

zbMATH Keywords

chromatic numberparameterized complexitygraph decompositions

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (4)

Competitive Algorithms for Generalized k -Server in Uniform Metrics ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

Uses Software

• gCol

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Between treewidth and clique-width
• Data reduction for graph coloring problems
• Matching is as easy as matrix inversion
• Colorings and orientations of graphs
• Some simplified NP-complete graph problems
• A partial k-arboretum of graphs with bounded treewidth
• The vertex separation and search number of a graph
• A note on graph colorings and graph polynomials
• Which problems have strongly exponential complexity?
• Tree-width, path-width, and cutwidth
• Searching and pebbling
• Edge dominating set and colorings on graphs with fixed clique-width
• Gröbner bases and graph colorings
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Parameterized Algorithms for Modular-Width
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Intractability of Clique-Width Parameterizations
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Set Partitioning via Inclusion-Exclusion
• Bounding the Independence Number of a Graph
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• Cutwidth: obstructions and algorithmic aspects
• Guide to Graph Colouring
• Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms
• On the complexity of \(k\)-SAT
• gCol

This page was built for publication: Computing the chromatic number using graph decompositions via matrix rank