Another infinite sequence of dense triangle-free graphs

Stephan Brandt

FB Mathematik & Informatik, WE 2 Freie Universität Berlin Arnimallee 3, 14195 Berlin, Germany

                     brandt@math.fu-berlin.de

Tomaž Pisanski

University of Ljubljana Faculty of Mathematics and Physics and IMFM/TCS Jadranska 19, Ljubljana, Slovenia

                   Tomaz.Pisanski@fmf.uni-lj.si

Submitted: February 26, 1998; Accepted: July 27, 1998 AMS Subject classifications: 05C75, 05C35

Abstract

The core is the unique homorphically minimal subgraph of a graph. A triangle-free graph with minimum degree δ > n/3 is called dense. It was observed by many authors that dense triangle-free graphs share strong structural properties and that the natural way to describe the structure of these graphs is in terms of graph homomorphisms. One infinite sequence of cores of dense maximal triangle-free graphs was known. All graphs in this sequence are 3colourable. Only two additional cores with chromatic number 4 were known. We show that the additional graphs are the initial terms of a second infinite sequence of cores.

Let G and H be graphs. A homomorphism G → H is a function σ : V (G) → V (H) mapping edges on edges, i.e. vw ∈ E(G) implies σ(v)σ(w) ∈ E(H). Every graph G has a unique minimal subgraph G′ with G → G′ which is called the core (for an introduction and relevant literature see [6]). Note that the core of G has the same chromatic number as G.

A triangle-free graph is maximal, if for every pair of non adjacent vertices u, v the addition of the edge uv creates a triangle. Note that a triangle-free graph of order n ≥ 3 is maximal, if and only if it has diameter 2. Let u_{1}, u_{2} be two non-adjacent vertices of a maximal triangle-free graph G. Assume that there is a vertex v_{1} which is adjacent to u_{1} but not to u_{2}. Since u_{2} and v_{1} are not adjacent, they must have a common neighbour v_{2}. Therefore σ(u_{1}) ≠ σ(u_{2}) for any homomorphism σ from G to a triangle-free graph. It follows that σ(w_{1}) = σ(w_{2}) implies that the set of neighbours of w_{1} is the same as the set of neighbours of w_{2}. Two vertices sharing the same neighbourhood have been called twins (or similar, or symmetric).

The “twin” relation is an equivalence relation on the vertex set of a graph where every equivalence class forms an independent set. The identification of twins in any order eventually leads to the unique maximal twin-free induced subgraph which coincides with the core if the graph is maximal triangle-free. Hence the core of a maximal triangle-free graph G is obtained by successively identifying twins until no twins remain.

The reverse operation to twin identification is vertex duplication where at each step a new twin is added to a vertex. The final result depends only on the number of times a vertex is duplicated and not on the order of the duplications. Hence the result is uniquely described if we assign positive integers to the vertices of the original graph, each integer specifying the number of duplicates including the original vertex. In case of a core, the numbers represent the cardinalities of the equivalence classes of the “twin” relation.

A triangle-free graph of order n with minimum degree δ > n/3 will be called dense. Chen, Jin and Koh [4] characterized the dense maximal triangle-free 3-colourable graphs in terms of their cores (see Brandt [2] for a much simpler proof).

Figure 1: The Grötzsch graph Υ_{11} and the Jin graph Υ_{12}.

Only two 4-chromatic cores of dense maximal triangle-free were known, one being the Grötzsch graph, detected by Häggkvist [5], and the other being the graph, which was found by Jin [8]; see Figure 1.

The objective of this note is to show that these two graphs are the initial terms of an infinite sequence of 4-chromatic cores of dense maximal triangle-free graphs. In fact, we show that for every p ≥ 11 there exists a 4-chromatic graph Υ_{p} on p vertices being the core of a dense triangle-free graph.

Let us start with describing an infinite sequence Γ_{k}, of 3-colourable dense maximal triangle-free cores. Later these graphs will appear as building blocks in the new sequence Υ_{p}.

For k ≥ 1 let Γ_{k} denote the Cayley graph over Z_{3k−1} with respect to the set of generators {i : k ≤ i ≤ 2k − 1}. These graphs are complements of cycle powers, defined as follows. Let Γ_{1} = K_{2} and, for k ≥ 2, Γ_{k} = \overline{C_{3k−1}^{k−1}}, i.e. Γ_{k} is the complement of the (k − 1)st power of the 3k − 1 cycle. As usual, the kth power G^{k} of a graph G is the graph on V (G), where v and w are adjacent if and only if their distance in G is at most k. Clearly, Γ_{2} = C_{5}, the 5-cycle and Γ_{3} is the Möbius ladder on 8 vertices. The graph Γ_{k} can also be described as the Cayley graph over Z_{3k−1} with respect to the set of generators {3i − 2 : 1 ≤ i ≤ k}. We will make use of this representation, by assuming that Γ_{k} has vertex set {w_{0}, …, w_{3k−2}} where w_{i}w_{j} ∈ E(Γ_{k}) iff |i − j| ≡ 1 (mod 3).

This sequence of graphs was probably first discovered by Andrásfai and Erdős (see [1]) in 1962 and has been rediscovered several times throughout the years. In 1981, Pach [9] observed that the triangle-free graphs where every independent set of vertices is contained in the neighbourhood of a vertex are precisely those which can be obtained from a graph Γ_{k} by consecutively duplicating vertices. Pach’s result was recently rediscovered by Brouwer [3], giving a much shorter proof. In [2], the first author observed that these graphs can be alternatively characterized as those maximal triangle-free graphs which do not contain an induced 6-cycle.

Note that the core is invariant under vertex duplications, since the vertex and its twin can be identified by a homomorphism. Generalizing a result of Jin [7], Chen, Jin and Koh [4] proved that the core of every 3-colourable dense maximal triangle-free graph is a graph Γ_{k}. So the question arose whether it is possible, to characterize the cores of dense triangle-free graphs with chromatic number at least 4 as well. It was proven by Chen, Jin and Koh [4] that every such graph contains the Grötzsch graph as an induced subgraph (see also [2] for a simple proof of these results). Using the computer program Vega [10], we computed further graphs which are cores of dense maximal triangle-free 4-chromatic graphs, and we observed that they belong to an infinite sequence of such graphs, which we will call, due to their origin, Vega graphs.

For every p ≥ 11 there exists a Vega graph Υ_{p} with p vertices which is obtained in the following way:

For k ≥ 4 and p = 3k + 1 take a 6-cycle C = (v_{1}, v_{2}, …, v_{6}), an edge u_{1}u_{2} and a copy of Γ_{k−2} with vertex set {w_{1}, w_{2}, …, w_{3k−7}}. Join u_{1} to v_{1}, v_{3}, v_{5}, u_{2} to v_{2}, v_{4}, v_{6} and w_{3i−j} to v_{3−j} and v_{6−j} for 1 ≤ i ≤ k − 2 and 0 ≤ j ≤ 2. The resulting graph is Υ_{3k+1}; see Figure 2 for the case k = 5.

In order to obtain Υ_{3k} delete the vertex w_{1} from Υ_{3k+1}, and to obtain Υ_{3k−1} delete the vertex u_{1} from Υ_{3k}. Now we can state our main result:

Theorem 1 For every p ≥ 11 there is a triangle-free graph with chromatic number 4 of order p = 3k+ℓ, −1 ≤ ℓ ≤ 1, which is the core of a triangle-free (9k−25+ℓ)-regular graph on n = 27k − 76 + 3ℓ vertices.

Proof. We claim that the Vega graphs Υ_{p}, p ≥ 11, have the indicated property. First we show that Υ_{p} is its own core, which follows from the fact that Υ_{p} is maximal Figure 2: Υ_{16} is composed of two parts. The graph on 8 vertices on the left to which Γ_{8} is attached on the right.

triangle-free and the neighbourhood of no vertex is contained in the neighbourhood of another vertex. This can be derived from the fact that the graphs Γ_{k} do have this property, combined with a simple case analysis. In particular, Υ_{p} is the core of every graph G which is homomorphic with Υ_{p} and which contains Υ_{p} as a subgraph.

It is left to show that for every p ≥ 11 there is a regular dense maximal trianglefree graph whose core is Υ_{p}. We do this by duplicating vertices according to an appropriate weight assignment.

Let us start assigning the weights to Υ_{3k+1} and then modify the weights for the cases p = 3k and p = 3k − 1. For p = 3k + 1 assign weight 1 to each vertex u_{i} and to the vertices w_{1} and w_{3k−7}, weight 3 to the vertices w_{i} for 2 ≤ i ≤ 3k − 8, weight 3k − 9 to v_{3} and v_{6}, and weight 3k − 8 to v_{1}, v_{2}, v_{4}, v_{5}. The result (by duplicating the vertices the right number of times) is a (9k − 24)-regular graph of order 27k − 73. For p = 3k (where the vertex w_{1} is deleted), leave the labels unchanged except for w_{2} and w_{3k−7} which both get weight 2, and v_{1} and v_{4} which both get weight 3k − 9. The result is a (9k − 25)-regular graph of order 27k − 76. Finally, the case p = 3k − 1. Here u_{1} is additionally deleted. We leave the labels unchanged, except for u_{2} which gets label 2, v_{1} and v_{3}, which get label 3k − 10 and v_{5}, which gets label 3k − 9. The result is a (9k − 26)-regular graph of order 27k − 79. □

Finally, we would like to know whether there are further cores of dense maximal triangle-free graphs. If not then the answer to the following problem was affirmative (note that every graph Γ_{k} is a subgraph of Υ_{3k+7}).

Problem 1 Is every triangle-free graph with minimum degree δ > n/3 homomorphic with a graph Υ_{p}?

As a consequence this would imply that every triangle-free graph with minimum degree δ > n/3 is 4-colourable, in contrast to a conjecture of Jin [8], saying that there are graphs of arbitrarily large chromatic number with this property.

References

[1] B. Andrásfai, Über ein Extremalproblem der Graphentheorie, Acta Math. Acad. Sci. Hungar. 13 (1962), 443–455.

[2] S. Brandt, On the structure of dense triangle-free graphs, Preprintreihe Mathematik, No. A 97–16, 1997, to appear in Comb., Prob. and Comp.

[3] A. Brouwer, Finite graphs in which the point neighbourhoods are the maximal independent sets, in: From universal morphisms to megabytes: a Baayen space odyssey (K. Apt, ed.), CWI Amsterdam, 1995, pp. 231–233.

[4] C. C. Chen, G. Jin and K. M. Koh, Triangle-free graphs with large degree, Comb., Prob. and Comp. 6 (1997), 381–396.

[5] R. Häggkvist, Odd cycles of specified length in non-bipartite graphs, Ann. Discr. Math. 13 (1982), 89–99.

[6] P. Hell and J. Nešetřil, The core of a graph, Discrete Math. 109 (1992), 117–126.

[7] G. Jin, Triangle-free graphs with high minimal degrees, Comb. Prob. and Comp. 2, (1993), 479–490.

[8] G. Jin, Triangle-free four-chromatic graphs, Discrete Math. 145 (1995), 151– 170.

[9] J. Pach, Graphs whose every independent set has a common neighbour, Discrete Math. 37 (1981), 217–228.

[10] T. Pisanski (ed.), Vega Version 0.2; Quick Reference Manual and Vega Graph Gallery, IMFM, Ljubljana, 1995. http://vega.ijp.si/