Computing the chromatic number using graph decompositions via matrix rank

Bart M.P. Jansen, Jesper Nederlof

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
154 Downloads (Pure)


Computing the smallest number q such that the vertices of a given graph can be properly q-colored 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. We present two algorithms for q-COLORING parameterized by cutwidth ctw: a deterministic one that runs in time O(2ω·ctw), where ω is the matrix multiplication constant, and a randomized one with runtime O(2ctw). In sharp contrast to earlier work, the running time is independent of q. The dependence on cutwidth is optimal: we prove that even 3-COLORING cannot be solved in O((2 - ϵ)ctw) time assuming SETH. Our algorithms rely on a new rank bound for a matrix that describes compatible colorings. Combined with a simple communication protocol for evaluating a product of two polynomials, this also yields an O((⌊d/2⌋ + 1)pw) time randomized algorithm for q-COLORING on graphs of pathwidth pw and maximum degree d. Such a runtime was first obtained by Björklund, but only for graphs with few proper colorings. We also prove that this result is optimal in the sense that no O((⌊d/2⌋ +1-ϵ)pw)-time algorithm exists assuming SETH.

Original languageEnglish
Title of host publication26th European Symposium on Algorithms, ESA 2018
EditorsHannah Bast, Grzegorz Herman, Yossi Azar
Place of PublicationWadern
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages15
ISBN (Electronic)978-3-95977-081-1
Publication statusPublished - 1 Aug 2018
Event26th European Symposium on Algorithms, ESA 2018 - Helsinki, Finland
Duration: 20 Aug 201822 Aug 2018

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)


Conference26th European Symposium on Algorithms, ESA 2018


  • Chromatic number
  • Graph decompositions
  • Parameterized complexity


Dive into the research topics of 'Computing the chromatic number using graph decompositions via matrix rank'. Together they form a unique fingerprint.

Cite this