Paper Info
Title
Computing the Chromatic Number Using Graph Decompositions via Matrix Rank.
Abstract
Computing the smallest number q such that the vertices of a given graph can be properly q-colored, known as the chromatic number, is one of the oldest and most fundamental problems in combinatorial optimization. The q-Coloring problem has been studied intensively using the framework of parameterized algorithmics, resulting in a very good understanding of the best-possible algorithms for several parameterizations based on the structure of the graph. For example, algorithms are known to solve the problem on graphs of treewidth tw in time O⁎(qtw), while a running time of O⁎((q−ε)tw) is impossible assuming the Strong Exponential Time Hypothesis (SETH). While there is an abundance of work for parameterizations based on decompositions of the graph by vertex separators, almost nothing is known about parameterizations based on edge separators. We fill this gap by studying q-Coloring parameterized by cutwidth, and parameterized by pathwidth in bounded-degree graphs. Our research uncovers interesting new ways to exploit small edge separators.
Year
DOI
Venue
2018
10.1016/j.tcs.2019.08.006
Theoretical Computer Science
Keywords
DocType
Volume
Parameterized complexity,Chromatic number,Graph decompositions
Conference
795
Issue
ISSN
Citations 
112
0304-3975
0
PageRank 
References 
Authors
0.34
2
2
Name
Order
Citations
PageRank
Bart M. P. Jansen123220.86
Jesper Nederlof229424.22