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

Shift graphs, which were introduced by Erd\H{o}s and Hajnal, have been usedto answer various questions in extremal graph theory. In this paper, we provetwo new results using shift graphs and their induced subgraphs.  1. Recently Girao [Combinatorica2023], showed that for every graph $F$ withat least one edge, there is a constant $c_F$ such that there are graphs ofarbitrarily large chromatic number and the same clique number as $F$, in whichevery $F$-free induced subgraph has chromatic number at most $c_F$. Wesignificantly improve the value of the constant $c_F$ for the special casewhere $F$ is the complete bipartite graph $K_{a,b}$. We show that any$K_{a,b}$-free induced subgraph of the triangle-free shift graph $G_{n,2}$ haschromatic number at most $a+b$.  2. An undirected simple graph $G$ is said to have the AOP Property if it canbe acyclically oriented such that there is at most one directed path betweenany two vertices. We prove that the shift graph $G_{n,2}$ does not have the AOPproperty for all $n\geq 9$. We then construct induced subgraphs of shift graph$G_{n,2}$ with an arbitrarily high chromatic number and odd-girth which havethe AOP property. To the best of our knowledge, this gives the firstconstructive proof of the existence of graphs with arbitrarily high chromaticnumber and odd-girth that have the AOP property.  Furthermore, we construct graphs with arbitrarily high odd-girth that do nothave the AOP Property and also prove the existence of graphs with girth equalto $5$ that do not have the AOP property.

Shift Graphs, Chromatic Number and Acyclic One-Path Orientations