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

Given two graphs $H_1$ and $H_2$, a graph $G$ is $(H_1,H_2)$-free if itcontains no induced subgraph isomorphic to $H_1$ or $H_2$. Let $P_t$ be thepath on $t$ vertices and $K_t$ be the complete graph on $t$ vertices. Thediamond is the graph obtained from $K_4$ by removing an edge. In this paper weshow that every ($P_6$, diamond)-free graph $G$ satisfies $\chi(G)\le\omega(G)+3$, where $\chi(G)$ and $\omega(G)$ are the chromatic number andclique number of $G$, respectively. Our bound is attained by the complement ofthe famous 27-vertex Schl\"afli graph. Our result unifies previously knownresults on the existence of linear $\chi$-binding functions for several graphclasses. Our proof is based on a reduction via the Strong Perfect Graph Theoremto imperfect ($P_6$, diamond)-free graphs, a careful analysis of the structureof those graphs, and a computer search that relies on a well-knowncharacterization of 3-colourable $(P_6,K_3)$-free graphs.

An Optimal $\chi$-Bound for ($P_6$, diamond)-Free Graphs