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/

Zendy Plus

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

Zendy Tools

Zendy Open

The coloring problem (i.e., computing the chromatic number of a graph) can besolved in $O^*(2^n)$ time, as shown by Bj\"orklund, Husfeldt and Koivisto in2009. For $k=3,4$, better algorithms are known for the $k$-coloring problem.$3$-coloring can be solved in $O(1.33^n)$ time (Beigel and Eppstein, 2005) and$4$-coloring can be solved in $O(1.73^n)$ time (Fomin, Gaspers and Saurabh,2007). Surprisingly, for $k>4$ no improvements over the general $O^*(2^n)$ areknown. We show that both $5$-coloring and $6$-coloring can also be solved in$O\left(\left(2-\varepsilon\right)^n\right)$ time for some $\varepsilon>0$. Asa crucial step, we obtain an exponential improvement for computing thechromatic number of a very large family of graphs. In particular, for anyconstants $\Delta,\alpha>0$, the chromatic number of graphs with at least$\alpha\cdot n$ vertices of degree at most $\Delta$ can be computed in$O\left(\left(2-\varepsilon\right)^n\right)$ time, for some $\varepsilon =\varepsilon_{\Delta,\alpha} > 0$. This statement generalizes previous resultsfor bounded-degree graphs (Bj\"orklund, Husfeldt, Kaski, and Koivisto, 2010)and graphs with bounded average degree (Golovnev, Kulikov and Mihajilin, 2016).We generalize the aforementioned statement to List Coloring, for which noprevious improvements are known even for the case bounded-degree graphs.

Breaking the $2^n$ barrier for 5-coloring and 6-coloring