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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .