% Latex2e source for 5 page document
% Needs pictures gr.eps, jin.eps, v28.eps
\documentclass[12pt]{article}
\usepackage{graphicx,latexsym}
\topmargin 0pt
\headsep 0.25in
\textheight 9in
\textwidth 6in
\oddsidemargin 0in
\evensidemargin 0in
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 5 (1998), \#R43\hfill}
\thispagestyle{empty}
\newcommand{\qed}{\raisebox{-.8ex}{$\Box$}}
\newcommand{\dist}{{\rm dist}}
\newcommand{\diam}{{\rm diam}}
\newcommand{\quer}[1]{\overline{#1}}
\def\bigO{\math{\cal O}}
\def\epsi{\varepsilon}
\newtheorem{thm}{Theorem}
\newtheorem{conj}{Conjecture}
\newtheorem{lemma}{Lemma}
\newtheorem{coro}{Corollary}
\newtheorem{prob}{Problem}
\newenvironment{pf}%
{\noindent {\bf Proof.}}%
{\qed \medskip}
\newenvironment{pfq}%
{\noindent {\bf Proof.}}%
{\medskip}
\newenvironment{pfof}[1]%
{\noindent {\bf Proof of #1.
}}%
{\qed \medskip}
\title{Another infinite sequence of dense triangle-free graphs}
\author{Stephan Brandt\\
{\small FB Mathematik \& Informatik, WE 2}\\
{\small Freie Universit\"at Berlin}\\
{\small Arnimallee 3, 14195 Berlin, Germany}\\
{\small\tt brandt@math.fu-berlin.de}
\and
Toma\v{z} Pisanski\\
{\small University of Ljubljana}\\
{\small Faculty of Mathematics and Physics and IMFM/TCS}\\
{\small Jadranska 19, Ljubljana, Slovenia}\\
{\small\tt Tomaz.Pisanski@fmf.uni-lj.si}
}
\date{{\small Submitted: February 26, 1998; Accepted: July 27, 1998\\
AMS Subject classifications: 05C75, 05C35}}
\begin{document}
\maketitle
\begin{abstract}
The {\em core} is the unique homorphically minimal subgraph of a graph.
A triangle-free graph with minimum degree $\delta > n/3$ is called {\em 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 3-colourable. 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.
\end{abstract}
Let $G$ and $H$ be graphs. A {\em homomorphism} $G\to H$ is a function $\sigma:
V(G) \to V(H)$ mapping edges on edges, i.e.\ $vw\in E(G)$ implies
$\sigma(v)\sigma(w)\in E(H)$. Every graph $G$ has a unique minimal subgraph $G'$
with $G\to G'$ which is called the {\em core} (for an introduction and
relevant literature see~\cite{HN92}). Note that the core of $G$ has the
same chromatic number as $G$.
A triangle-free graph is {\em 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\ge 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 $\sigma(u_1) \ne \sigma(u_2)$ for any homomorphism $\sigma$ from $G$ to a
triangle-free graph. It follows that $\sigma(w_1) = \sigma(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 {\em 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 {\em 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 $\delta > n/3$
will be called {\em dense}.
Chen, Jin and Koh~\cite{CJK97} characterized the dense maximal triangle-free
$3$-colourable graphs in terms of
their cores (see Brandt~\cite{BraSdtg} for a much simpler proof).
\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.4\hsize]{gr.eps}
\includegraphics[width=0.4\hsize]{jin.eps}
%\epsa{8cm}{gr.eps}{}
\caption{The Gr\"otzsch graph $\Upsilon_{11}$ and the Jin graph $\Upsilon_{12}.$}
\end{center}
\end{figure}
Only two $4$-chromatic cores of dense maximal triangle-free were known, one being the
Gr\"otzsch graph, detected by H\"aggkvist~\cite{Hagg82}, and the
other being the graph, which was found by
Jin~\cite{Jin95}; 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 \ge 11$ there exists a $4$-chromatic graph $\Upsilon_p$ on $p$
vertices being the core of a dense triangle-free graph.
\bigskip
Let us start with describing an infinite sequence $\Gamma_k$, of 3-colourable
dense maximal triangle-free cores.
Later these graphs will appear as building blocks in the new sequence
$\Upsilon_p$.
For $k\ge 1$ let $\Gamma_k$ denote the Cayley graph over
${\bf Z}_{3k-1}$ with respect to the set of generators $\{ i: k \le i \le
2k-1\}$. These graphs are complements of cycle powers, defined
as follows. Let $\Gamma_1 = K_2$ and, for $k\ge 2$, $\Gamma_k =
\quer{C_{3k-1}^{k-1}}$, i.e.\ $\Gamma_k$ is the complement of the
$(k-1)$st power of the $3k-1$ cycle. As usual, the {\em $k$th 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, $\Gamma_2 = C_5$,
the 5-cycle and $\Gamma_3$ is the M\"{o}bius ladder on 8 vertices. The graph
$\Gamma_k$ can also be described as the Cayley graph over
${\bf Z}_{3k-1}$ with respect to the set of generators $\{ 3i-2 : 1\le i \le
k\}$. We will make use of this representation, by assuming that $\Gamma_k$
has vertex set $\{w_0,\ldots ,w_{3k-2}\}$ where $w_iw_j\in E(\Gamma_k)$
iff $|i-j| \equiv 1$ (mod $3$).
This sequence of graphs was probably first discovered by Andr\'asfai and
Erd\H{o}s (see~\cite{And62}) in 1962 and has been rediscovered
several times throughout the years. In 1981, Pach \cite{Pach81} 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 $\Gamma_k$ by consecutively duplicating
vertices.
Pach's result was recently
rediscovered by Brouwer~\cite{Brouw95}, giving a much shorter proof.
In~\cite{BraSdtg}, 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~\cite{Jin93}, Chen, Jin and Koh~\cite{CJK97}
proved that the core of every
$3$-colourable dense maximal triangle-free graph is a graph
$\Gamma_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~\cite{CJK97} that every such graph contains
the Gr\"otzsch graph as an induced subgraph (see also~\cite{BraSdtg} for a
simple proof of these results). Using the computer program Vega \cite{Vega},
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, {\em Vega graphs}.
For every $p\ge 11$ there exists a Vega graph $\Upsilon_p$ with $p$
vertices which is
obtained in the following way:
For $k\ge 4$ and $p=3k+1$ take a $6$-cycle $C = (v_1, v_2,\ldots ,
v_6)$, an edge $u_1u_2$ and a copy of $\Gamma_{k-2}$ with vertex set
$\{ w_1, w_2, \ldots, 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\le i\le k-2$ and $0\le j\le 2$.
The resulting graph is $\Upsilon_{3k+1}$; see Figure 2 for the case $k = 5$.
\begin{figure}
\begin{center}
\includegraphics[width=0.7\hsize]{v28.eps}
%\epsa{10cm}{v28.eps}{}
\caption{$\Upsilon_{16}$ is composed of two parts.
The graph on 8 vertices on the left to which $\Gamma_{8}$ is attached on the right.}
\end{center}
\end{figure}
In order to obtain $\Upsilon_{3k}$ delete the vertex $w_1$ from
$\Upsilon_{3k+1}$, and to obtain $\Upsilon_{3k-1}$ delete the vertex
$u_1$ from $\Upsilon_{3k}$. Now we can state our main result:
\begin{thm}
For every $p\ge 11$ there is a triangle-free graph with chromatic
number $4$ of order $p = 3k+\ell, -1 \le \ell \le 1$, which is
the core of a triangle-free
$(9k - 25 + \ell)$-regular graph on $n = 27k -76 + 3\ell$ vertices.
\end{thm}
\begin{pf}
We claim that the Vega graphs $\Upsilon_p$, $p\ge 11$, have the
indicated property. First we show that $\Upsilon_p$ is its own core,
which follows from the fact that $\Upsilon_p$ is maximal 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
$\Gamma_k$ do have this property, combined with a simple case analysis.
In particular, $\Upsilon_p$ is the core of every graph $G$ which is
homomorphic with $\Upsilon_p$ and which contains $\Upsilon_p$ as a
subgraph.
It is left to show that for every $p\ge 11$ there is a regular dense
maximal triangle-free graph whose core is $\Upsilon_p$.
We do this by duplicating vertices according to an
appropriate weight assignment.
Let us start assigning the weights to $\Upsilon_{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\le i\le 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$.
\end{pf}
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 $\Gamma_k$ is a subgraph of $\Upsilon_{3k+7}$).
\begin{prob}
Is every triangle-free graph with minimum degree $\delta > n/3$ homomorphic
with a graph $\Upsilon_p$?
\end{prob}
As a consequence this would imply that every triangle-free graph with
minimum degree $\delta>n/3$ is $4$-colourable, in contrast to a
conjecture of Jin~\cite{Jin95}, saying that there are graphs of
arbitrarily large chromatic number with this property.
\begin{thebibliography}{99}
\bibitem{And62}
{\sc B.\ Andr\'asfai,} \"Uber ein Extremalproblem der Graphentheorie, {\sl
Acta Math.\ Acad.\ Sci.\ Hungar.} {\bf 13} (1962), 443--455.
\bibitem{BraSdtg}
{\sc S.\ Brandt,} On the structure of dense triangle-free graphs,
Preprintreihe Mathematik, No.\ A 97--16, 1997, to appear in Comb.,
Prob.\ and Comp.
\bibitem{Brouw95}
{\sc 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.
\bibitem{CJK97}
{\sc C.~C.\ Chen, G.\ Jin and K.~M.\ Koh,} Triangle-free graphs with
large degree, {\sl Comb., Prob.\ and Comp.} {\bf 6} (1997), 381--396.
\bibitem{Hagg82}
{\sc R.\ H\"aggkvist,} Odd cycles of specified length in non-bipartite
graphs, {\sl Ann.\ Discr.\ Math.} {\bf 13} (1982), 89--99.
\bibitem{HN92}
{\sc P.\ Hell and J.\ Ne\v{s}et\v{r}il,} The core of a graph, {\sl
Discrete Math.} {\bf 109} (1992), 117--126.
\bibitem{Jin93}
{\sc G.\ Jin,} Triangle-free graphs with high minimal degrees, {\sl
Comb.\ Prob.\ and Comp.} {\bf 2}, (1993), 479--490.
\bibitem{Jin95}
{\sc G.\ Jin,} Triangle-free four-chromatic graphs, {\sl Discrete
Math.} {\bf 145} (1995), 151--170.
\bibitem{Pach81}
{\sc J.\ Pach,} Graphs whose every independent set has a common
neighbour, {\sl Discrete Math.} {\bf 37} (1981), 217--228.
\bibitem{Vega} {\sc T.\ Pisanski (ed.),} Vega Version 0.2; Quick Reference
Manual and Vega Graph Gallery, IMFM, Ljubljana, 1995.
{\tt http://vega.ijp.si/}
\end{thebibliography}
\end{document}