7
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\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
    Commented Aug 27, 2013 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
    Commented Aug 27, 2013 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
    Commented Aug 27, 2013 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
    Commented Aug 27, 2013 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
    Commented Aug 27, 2013 at 17:06

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 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
    Commented Jan 22, 2014 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
    Commented Jan 24, 2014 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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