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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.