FRUIT SALAD

András Gyárfás

Computer and Automation Institute Hungarian Academy of Sciences

                               Gyarfas@luna.aszi.sztaki.hu

Abstract. Paul Erdő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.

1. Nearly bipartite graphs.

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 ‘life’ to ‘theorem’), 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. ‘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 ⌊\frac{|S|}{2}⌋ − k independent vertices. Then, with some suitable function f, one can remove f(k) vertices from G so that the remaining graph is bipartite.’

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 nearly bipartite. 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 (P1 ): they do not contain two vertex disjoint odd cycles. Property P1 alone easily implies that the chromatic number of nearly bipartite graphs is at most five. In fact, K_{5} shows that P1 alone does not imply more. (If G is K_{5}-free then P 1 implies that χ(G) ≤ 4. This was conjectured by Erdős 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 (P2 ) of nearly bipartite graphs is that they do not contain an odd K_{4} , 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 P1 and P2 characterize nearly bipartite graphs. The proof relies on a theorem of Andrásfai ([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 α(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 ≥ 3 vertices. Every proper subgraph of G is nearly bipartite, but G is not, so α(G) < ⌊\frac{n}{2}⌋. If n is odd then deleting any vertex from G results in a graph G^{∗} which is nearly bipartite and

α(G) ≥ α(G^{∗}) ≥ \frac{n − 1}{2} = ⌊\frac{n}{2}⌋

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 ≥ 2 connected components. There is precisely one non-bipartite component C, because at least two contradicts property P1 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 ⌊\frac{|V (C)|}{2}⌋ 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 \frac{n}{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 α(G), then

α(G − e) = α(G) < \frac{n}{2}

which means that G − e is a counterexample, contradicting the choice of G. This means that G is an α-critical graph.

Observe that if G^{∗} is the graph obtained from G by removing two vertices of G then G^{∗} is nearly bipartite so

\frac{n}{2} − 1 ≤ α(G^{∗}) ≤ α(G) ≤ \frac{n}{2} − 1.

Thus equality holds everywhere, implying n = 2α(G) + 2.

In summary, we found that G must be a connected α-critical graph with n = 2α(G) + 2 vertices. A theorem of Andrásfai ([A], see also in [L], 8.25 ) states that such a graph must be an odd K_{4}. This contradicts property P2 and finishes the proof. *

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ős, 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 ≥ 3

r(n, n) = \{ \begin{matrix}2n if n = 4 or n is odd \\ 2n + 1 if n ≥ 6 and even \end{matrix}

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 ≡ 2 mod 4, the example is an odd K_{4} with 2n vertices, in which four edges of a C_{4} are subdivided with \frac{n}{2} − 1 vertices. The length of the smallest cycle is n + 1. For n ≡ 0 mod 4, the example is similar. Four edges of a C_{4} ⊂ K_{4} are subdivided with \frac{n}{2} −2 vertices and the two other edges of K_{4} are subdivided with 2 vertices. (Here n ≥ 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} ≤ ⌊\frac{|V (H)|}{2}⌋ + 1 ≤ 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 ≥ 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. *

2. A partition of bicolored complete graphs.

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

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 2-reachable in color i (i ∈ {1, 2}) if for any two distinct vertices of x, y ∈ 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 ⌈\frac{3n}{4}⌉ 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 ⌈\frac{n}{2}⌉ 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 red spanner if all vertices of K_{n} are adjacent in red to at least one end of e. The definition of a blue spanner is similar. Let R and 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} R, B are both non-empty. Then R and B form vertex disjoint bipartite graphs.

Proof. Assume that xy ∈ R and zy ∈ B. Then a red xz contradicts the definition of B and a blue xz contradicts the definition of R. Therefore R and B are vertex disjoint.

Assume that there is a cycle C in R. Let e be an edge of 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 R. This is possible only if C is an even cycle, so R is bipartite. Interchanging the roles of the colors in the argument we get that B is also bipartite. *

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 R is bipartite with bipartition [R_{1}, R_{2}] and 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} ∪ B_{j} with the smallest union.

3. Two edge disjoint monochromatic complete graphs.

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ős who asks immediately after finding a convenient place to sit down: ‘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?’(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: ‘not true, in our joint paper on Size-Ramsey numbers there is an easy lemma...’Ralph’s argument is accepted but Paul does not feel that the matter is settled. ‘Is it true for R(k)+1? ’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 ≤ f(k) ≤ R(k) + k − 1.

Next day we listened to Ralph proving that f(3) = 7 and f(4) ≤ 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ős 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) ∩ 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) \ 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 ≤ i ≤ 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} ∩ 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} \ 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} ∪ (M \ 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.

4. Chromatic bound on cycles and paths.

Szentendre, 1995. One year had gone by but in Paul’s book, like in Santa’s sack, there is always a new surprise. ‘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.’

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ø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 \ C is connected.

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

Case 1: G_{1} is bipartite. Since G_{1} is connected it has a unique bipartition V (G_{1}) = A∪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).

Case 2: 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}, …) and P_{2} = (p_{2}, …) 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} \ p_{1}, P_{2} \ p_{2}. If P_{3} reaches C_{1} before reaching any of P_{i} \ 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} \ 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. *

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

Acknowledgement. I am grateful to Paul Erdős, 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

[A] B.Andrásfai, On Critical Graphs, in Theory of Graphs, International Symposium, Rome, 1966 Ed.: P. Rosenstiehl, Gordon and Breach, New York, 1967, 1-9.

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

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

[EJ] P.Erdős, M.S.Jacobson, in preparation.

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

[FOW] T.Fowler, Finding Large Monochromatic Diameter Two Subgraphs. Manuscript.

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

[KHT] U.Krusenstjerna-Hafstrøm, B.Toft, Special subdivisions of K_{4} and 4-chromatic graphs, Monatsh. Math. 89 (1980) 101-110.

[L] L.Lovász, Combinatorial Problems and Exercises, North Holland, Amsterdam, 1979.

[S] L.Soltes, personal communication

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