Shift graphs, chromatic number and acyclic one-path orientations

Shift graphs, which were introduced by Erdős and Hajnal [9,11], have been used to answer various questions in structural graph theory. In this paper, we prove two new results using shift graphs and their induced subgraphs. [Figure presented] Recently Girão et al. [13], showed that for every graph F with at least one edge, there is a constant c_F such that there are graphs of arbitrarily large chromatic number and the same clique number as F, in which every F-free induced subgraph has chromatic number at most c_F. We significantly improve the value of the constant c_F for the special case where 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 has chromatic number bounded by O(log⁡(a+b)). [Figure presented] An undirected simple graph G is said to have the AOP Property if it can be acyclically oriented such that there is at most one directed path between any two vertices. We prove that the shift graph G_n,2 does not have the AOP property for any n⩾9. Despite this, we construct induced subgraphs of shift graph G_n,2 with an arbitrarily high chromatic number and odd-girth that have the AOP property. Furthermore, we construct graphs with arbitrarily high odd-girth that do not have the AOP Property and also prove the existence of graphs with girth equal to 5 that do not have the AOP property.