Skip to main content
3 of 4
eliminated undefined variable
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

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.