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.

  • $\begingroup$ I don't understand your restriction in the last paragraph... Is the trivial "connected" with $f(r)=r$ acceptable? $\endgroup$ – François G. Dorais Aug 27 '13 at 15:59
  • $\begingroup$ 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. $\endgroup$ – Daniel Soltész Aug 27 '13 at 16:39
  • $\begingroup$ OK. I think I had misread your last paragraph. Note that traceable graphs, as proposed by Gyárfás, can be quite large. $\endgroup$ – François G. Dorais Aug 27 '13 at 16:43
  • $\begingroup$ 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$ $\endgroup$ – Daniel Soltész Aug 27 '13 at 17:04
  • 1
    $\begingroup$ Yes, I just figured out you used $n$ for the size of $V(G)$ and not some fixed constant. Fixed now. $\endgroup$ – François G. Dorais Aug 27 '13 at 17:06

There is a very similar question to that of Gyarfas which is well-known, still open, and notoriously hard.

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$?

A positive answer to this question would directly imply the following conjecture of Gyarfas:

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)$.

  • 1
    $\begingroup$ 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.) $\endgroup$ – Daniel Soltész Jan 22 '14 at 9:34
  • 1
    $\begingroup$ You're of course right, my bad. You have to consider graphs of bounded clique number. I edited the post $\endgroup$ – Louis Esperet Jan 24 '14 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.