Computing the chromatic number using graph decompositions via matrix rank

DOI10.1016/j.tcs.2019.08.006zbMath1431.68053MaRDI QIDQ2330132

Jesper Nederlof, Bart M. P. Jansen

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 number; parameterized complexity; graph decompositions

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

68W20: Randomized algorithms

68Q27: Parameterized complexity, tractability and kernelization

Uses Software

• gCol

Cites Work

• gCol