Computing the Chromatic Number Using Graph Decompositions via Matrix Rank

DOI10.4230/LIPIcs.ESA.2018.47OpenAlexW2963291540MaRDI QIDQ5009610

Jesper Nederlof, Bart M. P. Jansen

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1806.10501

zbMATH Keywords

chromatic numberparameterized complexitygraph decompositions

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (1)

Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices

Uses Software

• gCol

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Between treewidth and clique-width
• Exact algorithms for exact satisfiability and number of perfect matchings
• 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
• A note on graph colorings and graph polynomials
• Which problems have strongly exponential complexity?
• Tree-width, path-width, and cutwidth
• 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
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• Cutwidth: obstructions and algorithmic aspects
• Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth
• 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

This page was built for publication: Computing the Chromatic Number Using Graph Decompositions via Matrix Rank