Computing the Chromatic Number Using Graph Decompositions via Matrix Rank

DOI10.4230/LIPICS.ESA.2018.47OpenAlexW2963291540MaRDI QIDQ5009610FDOQ5009610

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)

Cites Work

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

Cited In (2)

• Rank, term rank, and chromatic number
• Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices

Uses Software

• gCol

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5009610)