%This is an AMStex file for an 8 page document submitted
%to the Electronic Journal of Combinatorics, September 4, 1996
%Updated on February 12, 1997.

\magnification1200
\hsize=6.2truein
\vsize=652truept
\hoffset=0.1truecm
\font\smtt=cmtt8
\font\smcp=cmcsc8 
\headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics 4 (1997), \#R8\hfill\folio} \fi} 
\parskip=8pt
\line{\hfill}
\vskip1truecm
\def\Ccal{{\cal C}}
\def\newpage{\vfill\eject}
\def\title#1{\bigskip\centerline{\bf#1}}
\def\author#1{\bigskip\centerline{\bf #1}\medskip}
\def\address#1{\centerline{\it#1}}
\def\abstract#1{\vskip1truecm{\narrower\noindent{\bf Abstract.}
#1\bigskip}}
\def\references{\bigskip\noindent{\bf References}\bigskip}
\def\section #1\par{\bigskip\noindent{\bf #1}\bigskip}

\def\theorem #1 #2\par{\medskip
\noindent{\bf Theorem #1. \quad}{\sl#2}\par\medskip}

\def\lemma #1#2\par{\medskip
\noindent{\bf Lemma #1.\quad}{\sl#2}\par\medskip}

\def\corollary #1 #2\par{\medskip
\noindent{\bf Corollary #1. \quad}{\sl#2}\par\medskip}

\def\problem #1 #2\par{\medskip
\noindent{\bf Problem #1. \quad}{\sl#2}\par\medskip}
\def\conjecture #1 #2\par{\medskip
\noindent{\bf Conjecture #1. \quad}{\sl#2}\par\medskip}

\def\proposition #1 #2\par{\medskip
\noindent{\bf Proposition #1. \quad}{\sl#2}\par\medskip}

\def\remark {\medskip\noindent{\bf Remark. \quad}}
\def\proof{\noindent{\bf Proof.}$\;\;$}
\def\item #1#2\par{\medskip\noindent{\bf (#1)\quad}
{\sl#2}\par\smallskip}
\def\qed{\qquad{\bf *}\medskip}

\title{FRUIT SALAD}
\bigskip                            

\author{Andr\'as Gy\'arf\'as}
%\footnote{}{Supported by OTKA grant }

\address{Computer and Automation Institute}
\address{Hungarian Academy of Sciences}
\address{\smtt Gyarfas\@luna.aszi.sztaki.hu}


\abstract {Paul Erd\H{o}s liked fruit salad. I mixed  
this one for him from ingredients obtained while working on 
some of his problems. He was pleased by it and carried it 
to several places to offer to others as well. It is very sad 
that I have to add to the manuscript: dedicated to his 
memory. }
\vfill
%\eject
\bigskip

\bigskip
\noindent
\bf 1. Nearly bipartite graphs. \rm 

Szentendre, 1994. Although we are in the shade, the summer afternoon 
is very hot,
 the water Paul poured on 
the warm tiles of the terrace does not give too much relief. 
After reciting famous lines of a classical
Hungarian poet (slightly rewritten by 
changing \lq life\rq {}   to \lq theorem\rq {}), 
Paul feels it is time to read from his problem book. (This has 
nothing to do with the 
BOOK, to which even he had no free access.) Soon he reads 
something immediately awakening my senses numbed by the 
humidity. \lq A problem of Hajnal and myself: assume that $G$ is 
a graph in which every subset $S$ of vertices spans a 
subgraph with at least $\lfloor {|S|\over 2}\rfloor  -k$
 independent vertices.
Then, with some suitable function $f$, one can remove $f(k)$
vertices from $G$ so that the remaining graph is bipartite.\rq 

It is useful to look at special cases in the process
of becoming familiar with a problem. That is precisely what 
I am doing now, nearly two years after hearing the problem
from Paul. I am looking (and working without success) at the 
case $k=0$. Then we have a graph in which every subset of 
$2t$ vertices spans a subgraph with at least $t$ independent 
vertices (the condition for the odd subsets follows from this).
For easier reference, call these graphs 
\it nearly bipartite. \rm The problem is whether nearly bipartite
graphs become bipartite after the deletion of a constant number
of vertices (to justify the terminology). 
There is an example showing that the following conjecture, if 
true, is best possible.

\conjecture {1} {Nearly bipartite graphs can be made bipartite 
by the deletion of at most five vertices.}

It is immediate that 
nearly bipartite graphs have the following property (\it P1 \rm ): 
they
do not contain two vertex disjoint
odd cycles. Property  \it P1 \rm
 alone easily implies that the chromatic number 
of nearly bipartite graphs is at
 most five. In fact, $K_5$ shows that \it P1 \rm  alone does not 
imply more. (If $G$ is $K_5$-free then $P1$ implies that 
$\chi (G)\leq 4$. This was conjectured by Erd\H os and proved 
by Brown and Jung in [BJ].)
 However, it follows from a deep theorem of Folkman
 ([F]) that nearly bipartite graphs are at most $3$-chromatic. 
Another property (\it P2 \rm ) of nearly bipartite graphs
is that they do not contain an \it odd  $K_4$ \rm , which 
means a subdivision of $K_4$ 
in which all the six edges are subdivided 
with an even number of vertices. (Sometimes odd $K_4$-s 
are called fully odd $K_4$-s, here we use the shorter 
term.)
Odd $K_4$-s appear in many interesting conjectures and 
results. Toft in [T] conjectured that every $4$-chromatic 
graph contains an odd $K_4$. A special case was solved 
recently by Jensen and Shepherd (see [JS] which contains further 
references).
The next theorem shows that properties \it P1 \rm  and 
\it P2 \rm 
 characterize 
nearly bipartite graphs. The proof relies on a 
theorem of Andr\'asfai ([A]).

\theorem {1} {Assume $G$ is a graph without vertex disjoint 
odd cycles and without odd $K_4$-s. Then $G$ is nearly bipartite.}

\proof
Let $\alpha (G)$  denote the cardinality of a largest independent 
set of $G$.
Consider counterexamples for Theorem 1 
of minimum order and within those
select a graph $G$ with minimum size. Clearly, $G$ has $n\geq 3$ 
vertices. 
Every proper subgraph of $G$ is nearly 
bipartite, but $G$ is not, so $\alpha (G) < 
\lfloor {n \over 2} \rfloor $. 
 If $n$ is odd then deleting any vertex from $G$ 
results in a graph $G^*$ which is nearly bipartite and 
$$
\alpha (G) \geq \alpha (G^*) \geq {n-1 \over 2}= 
\left\lfloor {n \over 2} \right\rfloor
$$
contradicting to the assumption that $G$ is a counterexample.
Thus $n$ must be even. 

Next we show that $G$ must be connected. Assume indirectly that 
$G$ has $t\geq 2$ connected components. There is
 precisely one non-bipartite component $C$, because at least
two contradicts property \it P1 \rm and zero contradicts 
the choice of $G$.  But $G[C]$ is a proper subgraph of $G$ 
so there is an independent set $S$ in $G[C]$ with at least 
$ \lfloor {|V(C)|\over 2} \rfloor $ vertices. Then $S$ can 
be extended by the majority color classes of the other 
(bipartite) components to an independent set of $G$ with 
at least ${n \over 2}$ vertices. This contradicts the definition 
of $G$ and we conclude that $G$ must be connected.

 If there is an edge $e$ of $G$ whose removal 
does not increase $\alpha (G)$, 
 then
$$
\alpha (G - e) = \alpha (G) <  {n \over 2} 
$$
which means that $G-e$ is a counterexample, contradicting 
 the choice of $G$. This means that $G$ is an 
$\alpha $-critical graph.

Observe that if $G^*$ is the graph obtained from $G$ by 
removing two vertices of $G$ then $G^*$ is nearly 
bipartite so 
$$
{n\over 2}-1\leq \alpha (G^*) \leq \alpha (G) \leq {n\over 2}-1.
$$
Thus equality holds everywhere, implying 
$n=2\alpha (G)+2$. 

In summary, we found that $G$ must be a connected 
$\alpha $-critical graph with $n=2\alpha (G)+2$ vertices. 
A theorem of Andr\'asfai ([A], see also in [L], 8.25 )
states that such a graph must be 
an odd $K_4$. This contradicts property \it P2 \rm and 
finishes the proof.
\qed

Theorem 1 can be applied to get a connection 
between the girth and the independence number of 
a graph. This can be formulated as a Ramsey type problem, 
introduced by Erd\H os, Faudree, Rousseau and Schelp in [EFRS]. 
Let $r(m,n)$ be the smallest $p$ for which every graph
of order $p$ contains either a cycle of length at most $m$ or 
$n$ independent vertices. In case  $n<m<2n-1$, it was proved
in [EFRS] that $r(m,n)=2n$, with a nice proof which relied on 
Kuratowski's characterization of planar graphs. 
The next theorem gives the diagonal case, in fact, it 
also gives a different proof for the cited result.  
(Probably 
this works both ways, i.e. Theorem 2 can be 
proved with the method in [EFRS].)       

\theorem {2} {For any integer $n\geq 3$ 
$$
r(n,n)=
\left\{ \aligned  2n \text{ if } n=4 \text{ or } 
n \text { is odd } \\ 
                  2n+1  \text{ if } n \geq 6 \text{ and even }  
                    \endaligned
\right.
$$
}

\proof
First examples are given to show that the claimed 
values can not be lowered.
For odd $n$ and for $n=4$ we can take 
 the cycle $C_{2n-1}$ which obviously contains 
neither a cycle of length at most $n$  nor an 
independent set of $n$ vertices. 

For $n \equiv 2 \mod 4$, 
the example is an odd $K_4$ with $2n$ vertices, 
in which four edges of 
a $C_4$ are subdivided with ${n \over 2}-1$ vertices. 
The length of the smallest cycle is 
$n+1$.
For $n \equiv 0 \mod 4$, the example is  
similar.  Four edges of a $C_4 \subset K_4$ are 
subdivided with ${n\over 2}-2$ vertices and the two 
other edges of $K_4$ are subdivided with $2$ vertices. 
(Here $n\geq 8$ is needed because the smallest cycle is
of length $min \{2n-4,n+2\}$ which does not exceed 
$n$ for $n=4$). In both cases we have an odd $K_4$ with
$2n$ vertices which does not contain an independent set 
of $n$ vertices. 


Let $G$ be a graph with $N$ vertices, where 
$N=2n$ if $n$ is odd or $n=4$ and $N=2n+1$ otherwise. 
If $G$ has two vertex disjoint odd cycles then one of 
them is of length at most $n$. 

Assume that $G$ contains a subgraph $H$ 
which is an odd $K_4$. By summing the lengths $l_i$ of 
 the four odd cycles $C_1,C_2,C_3,C_4$ defined
 by three base points and their connecting paths in $H$
it is easily seen that the smallest $l_i$, say $l_1$ 
satisfies
 
$$l_1\leq \left\lfloor {|V(H)|\over 2} \right\rfloor +1
\leq  n+1
$$
(in the last step, we used that $|V(H)|$ is even and 
at most $2n+1$).

However, it is impossible that $l_1=n+1$. 
Indeed, if $n$ is odd then  
$l_1=n+1$ contradicts the fact that $l_1$ is odd.
 For even $n$ we may assume that $|V(H)|=2n$
and $l_i=n+1$ for all $i$. 
If $n=4$ then at most two edges of the base $K_4$ of $H$ 
have nontrivial subdivisions therefore  
there is a cycle of length four using four edges of the base.
For even $n\geq 6$ induction works easily. Let $v$ be the 
vertex of $G$ not in $H$. If $v$ has degree at least two 
in $G$ then $v$ sends two edges to one of the cycles 
$C_i$. This immediately gives a cycle of length at most $n$
because each $C_i$ is of length $n+1$. Therefore $v$ is of 
degree at most one so deleting $v$ and its possible 
neighbor from $G$ we get a graph $G^*$ with $2n-1$ vertices.
Then, by induction, $G^*$ has either a cycle of length at most 
$n-1$ or an independent set of $n-1$ vertices. The former case
gives the required cycle for $G$ otherwise $v$ extends the 
independent set to size $n$ in $G$.

The conclusion is that $G$ contains neither vertex disjoint 
odd cycles nor an odd $K_4$. Then, by Theorem 1, $G$ is nearly 
bipartite so $G$ has an independent set of size $n$ completing
the proof. \qed 

\medskip
\noindent
\bf 2. A partition of bicolored complete graphs. \rm

Memphis, 1994 December. 
\lq I ran into this problem by misunderstanding a question 
 of Duke and Fowler\rq - explains Paul in a phone call 
from Atlanta.  
\lq Assume that the edges of the complete graph $K_n$ are 
colored with red and blue. Can we find 
a monochromatic subgraph of ${3n\over 4}$ vertices
 which has diameter $2$? There is an example 
showing that this would be best possible.\rq 

The example comes by partitioning evenly 
the vertex set of $K_n$ into four sets $A_i$. Color all edges 
of the complete bipartite graphs $[A_1,A_2]$, $[A_2,A_3]$, 
$[A_3,A_4]$ red and color all edges of the complete bipartite 
graphs $[A_3,A_1]$, $[A_1,A_4]$, $[A_4,A_2]$ blue. The color 
of the other edges can be arbitrary. 

I could prove only a weaker statement (Proposition 1) with a 
simple proof which also gives a related result (Proposition 2).   
The original question was eventually settled affirmatively 
by Fowler ([F]), he also treated the case of more than 
two colors.

A subset $A$ of vertices in a $2$-colored $K_n$ is called 
\it $2$-reachable \rm in color $i$ ($i\in \{ 1,2\}$) if for any
 two 
distinct vertices of $x,y\in A$ there is path of length at most two 
in color $i$ with endpoints $x,y$. (Observe that $A$ does 
not necessarily span a diameter $2$ subgraph in color $i$ 
because the middle vertex of a path of length two in color $i$  
may be outside of $A$.)

\proposition {1} {In any $2$-colored $K_n$ there is a subset
of at least $\lceil {3n\over 4} \rceil$ vertices which is 
 $2$-reachable in one of the colors. }

Notice that although Proposition 1 is weaker than the original
 conjecture, Fowler's theorem, 
but it is still best possible, as shown by the same example given 
above. 
 The proof also gives the following proposition 
(which is also best possible).

\proposition {2} {A $2$-colored $K_n$ is either of diameter $2$
in one of the colors or there is a subset of 
 $\lceil {n\over 2} \rceil$ vertices which is $2$-reachable in both
  colors.}

Both propositions follow from a simple 
lemma about partitioning the vertices of $2$-colored complete
 graphs.
 Call a red edge $e$
of a $2$-colored $K_n$ a \it red spanner \rm if all vertices 
of $K_n$ are adjacent in red to at least one end of $e$.
The definition of a \it blue spanner \rm is similar.
Let $\Cal R$ and $\Cal B$ denote the 
set of red and blue spanners in a $2$-colored $K_n$.

\lemma {1} {Assume that in a  $2$-colored $K_n$  
$\Cal R,\Cal B$ are both non-empty. Then $\Cal R$ and
 $\Cal B$ form vertex disjoint bipartite graphs.}

\proof
Assume that $xy\in \Cal R$ and $zy \in \Cal B$. Then 
a red  $xz$ contradicts the definition of $\Cal B$ and 
a blue $xz$ contradicts the definition of $\Cal R$.
Therefore $\Cal R$ and $\Cal B$ are vertex disjoint.

Assume that there is a cycle $C$ in $\Cal R$. 
Let $e$ be an edge of $\Cal B$, it is  vertex 
disjoint from $C$. Each vertex of $C$ is adjacent to some 
end of $e$ in blue from the definition of $e$. But two 
consecutive vertices of $C$ can not be adjacent in blue 
to the same end of $e$ because the edges of $C$ are in 
$\Cal R$. This is possible only if $C$ is an even cycle, 
so $\Cal R$ is bipartite. Interchanging the roles of 
the colors
in the argument we get that $\Cal B$ is also bipartite.
\qed

Consider a $2$-colored $K_n$. If one of the 
spanners is empty then we have  
a monochromatic
diameter two subgraph with $n$ vertices.
Otherwise, from Lemma 1, the vertices of $K_n$ can be 
partitioned into $R_1,R_2,B_1,B_2$ so that 
$\Cal R$ is bipartite with bipartition $[R_1,R_2]$ and 
$\Cal B$ is bipartite with bipartition $[B_1,B_2]$. Now 
a subset required for Proposition 1 can be obtained by 
deleting a smallest among the four sets and a subset 
required for Proposition 2 can be obtained by deleting 
$R_i \cup B_j$ with the smallest union.  
 


\noindent
\bf 3. Two edge disjoint monochromatic complete graphs. \rm

Atlanta, Airport, March, 1995.  
What can you do
at the Atlanta Airport if you have to wait four hours for the
connecting flight? 
You have no options assuming
you are a mathematician in the company of Paul Erd\H os who 
asks immediately after finding a convenient place to sit
down: \lq is it true that if you $2$-color the edges of a
 complete
graph on $R(k)$ vertices then there are two edge disjoint
monochromatic complete subgraphs on $k$ vertices?\rq (Paul 
rightly assumes
that in the company everybody knows that $R(k)$ is
the smallest integer $m$ with the property: 
if the edges of $K_m$ are colored with two colors in any 
fashion then there is a 
monochromatic $K_k$.)    
After some minutes of thought Ralph Faudree answers: \lq not 
true, in our joint paper on Size-Ramsey numbers there is 
an easy lemma...\rq Ralph's argument is accepted but Paul does
not feel that the matter is settled. \lq Is it true for 
$R(k)+1$? \rq   
Pads are out of the handbags and from now on your only worry
is not to miss your connecting flight. 
Three hours later the state of the art is: 
if $f(k)$ is the smallest $m$ 
for which there are two edge disjoint monochromatic $K_k$-s 
in every two-coloring of the edges of $K_m$ then  
 $R(k)+1\leq f(k) \leq R(k)+k-1$.  

Next day we listened to Ralph proving that $f(3)=7$ and 
$f(4)\leq R(4)+2=20$. The next proposition confirms 
that $f(4)=R(4)+1=19$. L.Soltes ([S]) found a different proof
at the same time, relying on the result that the extremal coloring
of $K_{17}$ is unique. It seems doubtful whether $f(5)=R(5)+1$ 
can be decided without knowing $R(5)$. Erd\H os and Jacobson 
([EJ]) have results concerning edge disjoint 
monochromatic $K_k$-s in $2$-colorings of $K_n$.
 
\proposition {3} {f(4)=19.}

\proof
We may restrict ourselves to colorings of $K_{19}$ which
contain monofours in red only. We may also assume that
each vertex $x$ is a center of a monostar $S(x)$
with $10$ edges 
(otherwise the theorem follows from $R(3,4)=9$).

Case 1: some vertex $x$ sends precisely two red edges to a 
red monofour $M$ which does not contain $x$. Then removing at
most one vertex from $S(x)\cap M$ we have a monostar
of nine edges which intersects $M$ in at most one vertex
and  the theorem follows from $R(3,4)=9$. 

Case 2: there exists a (red) monofive $N$. Assume 
there are four vertices not in $N$ such that each sends
 at least three red edges to $N$. Since there are no blue
monofours, two vertices among the four determine a red edge
and then their union with $N$ obviously contains two
edge disjoint monofours. On the other hand, if at most three
vertices of $V(G)\setminus N$ send at least three red 
edges to $N$ then there are at least $11$ vertices
outside of $N$ sending at least three blue edges to $N$.
However, since we are not in case 1, each of these $11$
vertices sends at least four blue edges to $N$. This 
implies that some vertex of $N$ sends out at least $9$ 
blue edges and the theorem follows again from $R(3,4)$=9.

Assume that none of the cases above is applicable. Let $M$ be 
a (red) monofour with vertices $x_i$ ($1\leq i \leq 4$). 
Since $R(4,4)=18$, 
for each $i$, there exists a (red) monofour $M_i$ 
not containing $x_i$, under this restriction 
select $M_i$ so that  $t_i=|M_i\cap M|$
is as large as possible. If, for some $i$, $t_i < 2$ then 
the proposition follows. If, for some $i$, $t_i=2$ then 
let $x_j$ be the vertex of $M$ not in $M_i$ and different
from $x_i$. Since we are not in case 1, $x_j$ sends a red
edge to $M_i\setminus M$ which contradicts the choice of
$M_i$. We conclude that $t_i=3$ for all $i$ so each 
$M_i$ has vertex set $y_i \cup (M\setminus x_i)$ where
$y_i$ is a vertex not in $M$. The vertices $y_i$ are 
distinct since we are not in case 2. Since there are no
blue monofours, there is a red edge between two $y_i$-s, 
for example $(y_1,y_2)$ is a red edge. Now the 
sets $\{y_1,y_2,x_3,x_4\}$ and $\{x_1,x_2,x_3,y_4\}$
are edge disjoint (red) monofours, concluding the proof.


%\eject




%\eject
\medskip
\noindent
\bf 4. Chromatic bound on cycles and paths. \rm          

Szentendre, 1995. One year had gone by but in Paul's book, like
in Santa's sack, there is always a new surprise.
\lq A problem with Hajnal: if each odd cycle of a graph $G$  
spans a subgraph with chromatic number at most $r$ then
the chromatic number of the graph is bounded by a function of $r$.\rq 


If odd cycles are replaced by even cycles, then the first 
step gives the next result.
 

\proposition {4} {If each even cycle of a graph
spans a bipartite subgraph then the
graph is $3$-colorable.}



The proof is based on 
a result of Krusenstjerna-Hafstr\o m and Toft  ([KHT]): 

\theorem {KHT} {Every $4$-critical graph $G$
contains an induced odd cycle $C$ (odd cycle without
 diagonal)
such that $G_1=G\setminus C$ is connected. } 

\proof (of Proposition 4).
Assume that Proposition 4 is not true and select a $4$-critical 
counterexample
$G$. Clearly $G$ is $2$-connected 
with minimum degree at least $3$. 
Select $C$ according to Theorem KHT. 

\bf Case 1: \rm $G_1$ is bipartite. Since $G_1$ is connected it
 has
a unique bipartition $V(G_1)=A\cup B$. The assumption of
Proposition 4 implies that it is impossible that two 
consecutive vertices of $C$ are adjacent to $A$ or adjacent 
to $B$. This gives a contradiction
since each vertex of $C$ must be adjacent to a vertex of $A$ or 
to a vertex of $B$ (the minimum degree of $G$ is at least 
$3$).

\bf Case 2: \rm $G_1$ is not bipartite. Let $C_1$ be an odd cycle
 of 
$G_1$. The $2$-connectivity of $G$ implies that there exist
two vertex disjoint paths 
$P_1=(p_1,\dots )$ and $P_2=(p_2,\dots )$ in $G_1$ such that
both paths intersect $C$ and $C_1$ only at their endpoints.
Select these paths so that their endpoints, $p_1,p_2$ on $C$ 
are as 
close as possible. We claim that $p_1,p_2$ are consecutive on $C$.
Assume not, consider the shorter among the two paths connecting
$p_1,p_2$ on $C$, 
 there is an inner
 vertex $R$ on this path. Since $C$ is chordless and
$R$ is of degree at least three, $R$ is adjacent to a vertex $S$
of $G_1$. Because $G_1$ is connected, there exists a shortest 
path $P_3$ in $G_1$ from $S$ to the union of the 
paths  $P_1\setminus p_1$, 
$P_2\setminus p_2$. If $P_3$ reaches $C_1$ before reaching
any of $P_i\setminus p_i$ then $P_1$ and the path starting 
with the edge $RS$ and continuing on $P_3$ give two paths
from $C$ to $C_1$ contradicting the choice of $P_1$, $P_2$.
Similar contradiction arises if $P_3$ reaches 
say $P_1\setminus p_1$ before reaching $C_1$: in this case 
$P_2$ and the path starting with the edge $RS$ and using 
$P_3$ then continuing on $P_1$ lead to contradiction.
This finishes the proof of the claim.

Consider the even cycle $C^*$ 
  obtained
from the following paths:
the longer path connecting
$p_1,p_2$ on $C$; the paths $P_1,P_2$; the path of 
suitable parity connecting the endpoints of $P_1$ and $P_2$ 
on $C_1$. 
Clearly, $C^*$ contains all vertices of $C$ so it is an
even cycle spanning a non-bipartite graph. This final 
contradiction proves the proposition.
\qed

It seems that the following weaker version of the original 
problem (for $r=3$) is interesting.

\conjecture {2} If each path of a graph spans at most 
$3$-chromatic subgraph then the graph is $c$-colorable 
(with a constant $c$, perhaphs with $c=4$).

\noindent
\bf Acknowledgement. \rm I am grateful to Paul Erd\H os,
whose questions inspired the results and problems
of this paper. Conversations
with Ralph Faudree, Dick Schelp, Bjarne Toft about some of 
these subjects are also appreciated. The careful reading of 
the referee improved the presentation.

\references

\noindent
[A] B.Andr\'asfai, On Critical Graphs, in {\it 
Theory of Graphs, International Symposium, Rome, 
1966} Ed.: P. Rosenstiehl, Gordon and Breach, 
New York, 1967, 1-9.

\noindent
[BJ] W.G.Brown, H.A.Jung, On odd circuits in chromatic graphs, 
Acta Math. Acad. Sci. Hungar. 20, (1969) 129-134.

\noindent
[EFRS] P.Erd\H os, R.J.Faudree, C.C.Rousseau, R.H.Schelp, 
On Cycle-Complete Graph Ramsey Numbers, Journal of 
Graph Theory, 2 (1978) 53-64.

\noindent
[EJ] P.Erd\H os, M.S.Jacobson, in preparation.

\noindent
[FOL] J.H.Folkman, An upper bound on the chromatic number 
of a graph, Coll. Math. Soc. J. Bolyai 4. {\it 
Combinatorial Theory and its Applications} 437-457.

\noindent
[FOW] T.Fowler, Finding Large Monochromatic Diameter Two 
Subgraphs. Manu-script.

\noindent
[JS] T.R.Jensen, F.B.Shepherd, Note on a conjecture of Toft, 
Combinatorica, 3, (1995) 373-377.


\noindent
[KHT] U.Krusenstjerna-Hafstr\o m, B.Toft, Special subdivisions 
of $K_4$ and $4$-chromatic graphs, Monatsh. Math. 89 (1980)
101-110.

\noindent
[L] L.Lov\'asz, Combinatorial Problems and Exercises, North 
Holland, Amsterdam, 1979.

\noindent
[S] L.Soltes, personal communication

\noindent
[T] B.Toft, Problem 11, in {\it Recent Advances in Graph Theory} 
,Academia Praha 1975, 543-544.

\end
  
  
Andras Gyarfas
MTA SZTAKI Kende u. 13-17 Budapest 1111 Hungary
email: Gyarfas@luna.aszi.sztaki.hu Fax:  36 1 166 7503
Phone: 36 1 1665 644 ext. 107 Personal 36: 1 2027 028