# Chromatic number of induced subgraphs as upper bound to the chromatic number

Motivation: At the Erdős100 conference in Budapest András Gyárfás presented some interesting conjectures. One of them was the following:

Given that in a graph $G$, every subgraph $H$ formed by taking the induced subgraph on the vertices of a path, has chromatic number at most $r$. Is it true that then the chromatic number of $G$ is bounded by a function of $r$?

Question: Are there any results such that: If in a graph $G$, every induced subgraph with a special property has chromatic number at most $r$, then the chromatic number of $G$ is bounded by $f(r)$?

Of course i would like to avoid special properties that enable induced subgraphs with a lot of vertices, like the property that "This induced subgraph contains all but one vertex".

EDIT: Let $G$ be connected.

• I don't understand your restriction in the last paragraph... Is the trivial "connected" with $f(r)=r$ acceptable? – François G. Dorais Aug 27 '13 at 15:59
• No. That would do exactly the thing i was trying to avoid with my last paragraph. I will edit the question to avoid these kind of answers. I'm sorry about the badly formulated restrictions, i was trying to get results similar to the open problem in the second paragraph. – Daniel Soltész Aug 27 '13 at 16:39
• OK. I think I had misread your last paragraph. Note that traceable graphs, as proposed by Gyárfás, can be quite large. – François G. Dorais Aug 27 '13 at 16:43
• Now it's my turn to not understand things. I was trying to show that for example the property that "$H$ has $n-1$ vertices" is strong enough to bound the chromatic number of $G$ with $r+1$, but is not so interesting. Because it is very different from the open problem presented in the 'motivation'. It relies on the size of $H$ – Daniel Soltész Aug 27 '13 at 17:04
• Yes, I just figured out you used $n$ for the size of $V(G)$ and not some fixed constant. Fixed now. – François G. Dorais Aug 27 '13 at 17:06

Question: Is it true that if every triangle-free induced subgraph of $G$ has chromatic number at most $r$, then $G$ has chromatic number at most $f(r,\omega)$, where $\omega$ is the clique number of $G$?
Conjecture: There is a function $g$ such that every graph with no odd induced cycle of length at least 5, and clique number at most $k$, has chromatic number at most $g(k)$.
• Maybe i misunderstood something, but isn't the complete graph on $n$ vertices a counterexample to your first question? (Every triangle-free induced subgraph has at most $2$ vertices in the complete graph.) – Daniel Soltész Jan 22 '14 at 9:34