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 Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

We present an algorithm to color a graph $G$ with no triangle and no induced$7$-vertex path (i.e., a $\{P_7,C_3\}$-free graph), where every vertex isassigned a list of possible colors which is a subset of $\{1,2,3\}$. While thisis a special case of the problem solved in [Combinatorica 38(4):779--801,2018], that does not require the absence of triangles, the algorithm here isboth faster and conceptually simpler. The complexity of the algorithm is$O(|V(G)|^5(|V(G)|+|E(G)|))$, and if $G$ is bipartite, it improves to$O(|V(G)|^2(|V(G)|+|E(G)|))$.  Moreover, we prove that there are finitely many minimal obstructions to list3-coloring $\{P_t,C_3\}$-free graphs if and only if $t \leq 7$. This impliesthe existence of a polynomial time certifying algorithm for list 3-coloring in$\{P_7,C_3\}$-free graphs. We furthermore determine other cases of $t, \ell$,and $k$ such that the family of minimal obstructions to list $k$-coloring in$\{P_t,C_{\ell}\}$-free graphs is finite.

Better 3-coloring algorithms: excluding a triangle and a seven vertex path