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

For a graph $G$, $\chi(G)$ will denote its chromatic number, and $\omega(G)$its clique number. A graph $G$ is said to be perfectly divisible if for allinduced subgraphs $H$ of $G$, $V(H)$ can be partitioned into two sets $A$, $B$such that $H[A]$ is perfect and $\omega(H[B]) < \omega(H)$. An integer-valuedfunction $f$ is called a $\chi$-binding function for a hereditary class ofgraphs $\cal C$ if $\chi(G) \leq f(\omega(G))$ for every graph $G\in \cal C$.The fork is the graph obtained from the complete bipartite graph $K_{1,3}$ bysubdividing an edge once. The problem of finding a polynomial $\chi$-bindingfunction for the class of fork-free graphs is open. In this paper, we study thestructure of some classes of fork-free graphs; in particular, we study theclass of (fork,$F$)-free graphs $\cal G$ in the context of perfectdivisibility, where $F$ is a graph on five vertices with a stable set of sizethree, and show that every $G\in \cal G$ satisfies $\chi(G)\leq \omega(G)^2$.We also note that the class $\cal G$ does not admit a linear $\chi$-bindingfunction.

Coloring graph classes with no induced fork via perfect divisibility