2
$\begingroup$

The ordinary Turán problem for graphs asks, "Given a graph $H$, if $G$ is an $H$-free graph on $n$ vertices, what is the largest number of edges that $G$ can have?" As is well known, if $\chi(H) = r + 1$, then the maximum value is attained by the Turán graph $T_{r}(n)$, a nearly balanced complete $r$-partite graph.

I'm interested in a variant of this problem in which the chromatic number of $G$ is specified. Namely, if $r \geq 2$ and $G$ is a $K_{r+1}$-free graph on $n$ vertices with chromatic number $t \geq r + 1$, what is the largest number of edges that $G$ can have? I'm most interested in the case when $t = r + 1$.

When $r = 2$ and $t = 3$, the answer is well known: the maximum is $(n - 1)^2/4 + 1$, with equality holding, for example, in the case of a complete bipartite graph with a single edge subdivided.

This paper of Andrásfai, Erdős, and Sós says that the answer for all $r$ and $t$ is given by Erdős, Gallai, Andrásfai, and Simonovits in this paper. The latter paper answers the question for $r = 2$ and $t = 3$ (see Lemma 1), but, as far as I can tell, says nothing about the general case.

Does the result of Erdős et al. in the second paper extend (for any value of $t$) to $r \geq 3$? It's not obvious to me how to extend the proof given for $r = 2$ to higher values of $r$. In particular, the proof relies on three statements about $3$-critical graphs whose corresponding statements are either unknown or false for $(r + 1)$-critical graphs when $r + 1 \geq 4$:

  1. A simple characterization of 3-critical graphs (namely, odd cycles).
  2. The fact that adding an edge to a 3-critical graph creates a 3-critical graph on a smaller number of vertices.
  3. The fact that adding a vertex of large (constant) degree to a 3-critical graph creates a 3-critical graph on a smaller number of vertices.

Of these, the first is unknown for $r + 1 \geq 4$, and the second and third are false. (To see that the second is false, consider the Mycielski graph $M_{r+1}$, and to see that the third is false, consider the Mycielskian of a large $r$-chromatic graph.)

$\endgroup$
  • $\begingroup$ To have a complete answer to your question one would have to know for which values of $r,t,n$ there exists a $K_{r+1}$-free graph on $n$ vertices with chromatic number $t,$ right? I'm certainly no expert on graph coloring, but I would have thought that was an open problem even for $r=2.$ What is the minimum number of vertices for a $t$-chromatic triangle-free graph? $\endgroup$ – bof Oct 16 '15 at 17:30

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.