English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Computing the smallest number $q$ such that the vertices of a given graph canbe properly $q$-colored is one of the oldest and most fundamental problems incombinatorial optimization. The $q$-Coloring problem has been studiedintensively using the framework of parameterized algorithmics, resulting in avery good understanding of the best-possible algorithms for severalparameterizations based on the structure of the graph. While there is anabundance of work for parameterizations based on decompositions of the graph byvertex separators, almost nothing is known about parameterizations based onedge separators. We fill this gap by studying $q$-Coloring parameterized bycutwidth, and parameterized by pathwidth in bounded-degree graphs. Our researchuncovers interesting new ways to exploit small edge separators.  We present two algorithms for $q$-Coloring parameterized by cutwidth $cutw$:a deterministic one that runs in time $O^*(2^{\omega \cdot cutw})$, where$\omega$ is the matrix multiplication constant, and a randomized one withruntime $O^*(2^{cutw})$. In sharp contrast to earlier work, the running time isindependent of $q$. The dependence on cutwidth is optimal: we prove that even3-Coloring cannot be solved in $O^*((2-\varepsilon)^{cutw})$ time assuming theStrong Exponential Time Hypothesis (SETH). Our algorithms rely on a new rankbound for a matrix that describes compatible colorings. Combined with a simplecommunication protocol for evaluating a product of two polynomials, this alsoyields an $O^*((\lfloor d/2\rfloor+1)^{pw})$ time randomized algorithm for$q$-Coloring on graphs of pathwidth $pw$ and maximum degree $d$. Such a runtimewas first obtained by Bj\"orklund, but only for graphs with few propercolorings. We also prove that this result is optimal in the sense that no$O^*((\lfloor d/2\rfloor+1-\varepsilon)^{pw})$-time algorithm exists assumingSETH.

Computing the Chromatic Number Using Graph Decompositions via Matrix Rank