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

The Colouring problem asks whether the vertices of a graph can be colouredwith at most $k$ colours for a given integer $k$ in such a way that no twoadjacent vertices receive the same colour. A graph is $(H_1,H_2)$-free if ithas no induced subgraph isomorphic to $H_1$ or $H_2$. A connected graph $H_1$is almost classified if Colouring on $(H_1,H_2)$-free graphs is known to bepolynomial-time solvable or NP-complete for all but finitely many connectedgraphs $H_2$. We show that every connected graph $H_1$ apart from the claw$K_{1,3}$ and the $5$-vertex path $P_5$ is almost classified. We also prove anumber of new hardness results for Colouring on $(2P_2,H)$-free graphs. Thisenables us to list all graphs $H$ for which the complexity of Colouring is openon $(2P_2,H)$-free graphs and all graphs $H$ for which the complexity ofColouring is open on $(P_5,H)$-free graphs. In fact we show that these twolists coincide. Moreover, we show that the complexities of Colouring for$(2P_2,H)$-free graphs and for $(P_5,H)$-free graphs are the same for all knowncases.

On Colouring $(2P_2,H)$-Free and $(P_5,H)$-Free Graphs