% % January 24, 2000 % Version submitted to JCT B from SFU % % Uncomment the following 5 lines if AMS fonts are avail. % %\documentstyle[art12,amssymbols]{article} \documentstyle[11pt,amssymbols]{article} \newcommand{\QQ}{{\Bbb Q}}% \newcommand{\RR}{{\Bbb R}}% \newcommand{\QQP}{{\Bbb Q}_{\geq 0} }% \newcommand{\ZZ}{{\Bbb Z}}% \newcommand{\ZZP}{{\Bbb Z}_{\geq 0} }% \renewcommand{\baselinestretch}{1.4} % % Comment out the following 5 lines if AMS fonts are avail. % %\documentstyle[art12]{article}% %\newcommand{\QQ}{\mbox{\boldmath$\cal Q$}}% %\newcommand{\RR}{\mbox{\boldmath$\cal R$}}% %\newcommand{\QQP}{{\QQ}_{\geq 0} }% %\newcommand{\ZZ}{\mbox{\boldmath $\cal Z$}}% %\newcommand{\ZZP}{{\ZZ}_{\!\geq 0} }% \let\labl=\label %Comment out following line to get rid of marginal labels %\renewcommand{\label}[1]{\labl{#1}\{marginpar{\scriptsize{#1}}} \setlength{\textwidth}{6.3in} \setlength{\textheight}{8.8in} \setlength{\oddsidemargin}{0.0 in} \setlength{\evensidemargin}{0.0 in} \setlength{\topmargin}{0.0in} \setlength{\headheight}{0in} \setlength{\headsep}{0in} \flushbottom \newcommand{\kdc}{$(k,d\/)$-coloring }% \newcommand{\kdcs}{$(k,d\/)$-colorings }% \newcommand{\kdf}{$(k,d\/)$-flow }% \newcommand{\kdfs}{$(k,d)$-flows }% \newcommand{\w}{\omega}% \newcommand{\bs}{\backslash} \newcommand{\se}{\subseteq} \newcommand{\C}{{\cal C} }% \newcommand{\B}{{\cal B} }% \newcommand{\G}{\Gamma}% \newcommand{\res}[1]{{\langle #1 \rangle}} \newcommand{\norm}[1]{\left\|{#1}\right\|} \newcommand{\half}{{\frac{1}{2}}} \newtheorem{lemma}{\sc Lemma}[section]% \newtheorem{theorem}[lemma]{\sc Theorem}% \newtheorem{proposition}[lemma]{\sc Proposition}% \newtheorem{corollary}[lemma]{\sc Corollary}% \newtheorem{claim}[lemma]{\sc Claim}% \newtheorem{conjecture}[lemma]{\sc Conjecture}% \newtheorem{remark}[lemma]{\sc Remark}% \newtheorem{note}[lemma]{\sc Note}% \newtheorem{algorithm}[lemma]{\sc Algorithm}% \newtheorem{example}[lemma]{\sc Example}% \newtheorem{observation}[lemma]{\sc Observation}% \newtheorem{definition}[lemma]{\sc Definition}{}% \newtheorem{question}[lemma]{\sc Question}{}% \newtheorem{numbered}[lemma]{\sc}% \newenvironment{proof}{\noindent {\sc Proof.}}{$\Box$\par\medskip}% \input epsf \input psfig %\title{$H$-Minor-Free Graphs of High Girth} %%%%% Let's save the formal 'girth-bipartite' for the text only ?? %%%% %\title{Graphs Avoiding any Fixed Minor are Nearly Bipartite} %%%%Now it does not make sense any more!!!! Luis \title{High Girth Graphs Avoiding a Minor are Nearly Bipartite} \author{ Anna Galluccio\thanks{Supported by NATO-CNR Fellowship; this work was done mainly while the author was visiting the Dept. of Mathematics and Statistics at Simon Fraser University, Canada;}\\ {\normalsize Istituto di Analisi dei Sistemi ed}\\ {\normalsize Informatica - CNR}\\ {\normalsize Roma, Italy}\\ {\normalsize galluccio@iasi.rm.cnr.it}\\ \and Luis A. Goddyn\thanks{Supported by a National Sciences and Engineering Research Council Research Grant} \\ {\normalsize Department of Mathematics and Statistics}\\ {\normalsize Simon Fraser University}\\ {\normalsize Burnaby, B.C., Canada}\\ {\normalsize goddyn@math.sfu.ca}\\ \and Pavol Hell\thanks{Supported by a National Sciences and Engineering Research Council Research Grant} \\ {\normalsize Department of Mathematics and Statistics and}\\ {\normalsize School of Computing Science}\\ {\normalsize Simon Fraser University}\\ {\normalsize Burnaby, B.C., Canada}\\ {\normalsize pavol@cs.sfu.ca}\\ } \begin{document} \date{} \maketitle \bigskip {\bf AMS classifications (2000):} 05C15, (05C10, 05C83). \bigskip {\bf Proposed running head:} High girth nearly bipartite graphs. %{\Huge *** DRAFT 2: Not for distribution ***} %\newline{\tt .../Preprints/NearlyBipartite/draft2.tex } \newpage \begin{abstract} \normalsize Let $H$ be a fixed graph. We show that any $H$-minor free graph of high enough girth has a circular-chromatic number arbitrarily close to two. %%%%%% changed 'star' to circular%%%%% Equivalently, such graphs have homomorphisms into a large odd circuit. In particular, graphs of high girth and of bounded genus or bounded tree width are ``nearly bipartite'' in this sense. For example, any planar graph of girth at least 16 admits a homomorphism onto a pentagon. We also obtain tight bounds in a few specific cases of small forbidden minors. \bigskip {\bf Keywords:} homomorphisms, circular chromatic number, star chromatic number, girth, genus, series-parallel graphs. \end{abstract} \newpage {\bf Contact authors:} \noindent Anna Galluccio\\ Istituto di Analisi dei Sistemi ed Informatica - CNR\\ viale Manzoni 30 \\ 00185 Roma, Italy\\ galluccio@iasi.rm.cnr.it\\ or: \noindent Luis A. Goddyn\\ Department of Mathematics and Statistics\\ Simon Fraser University\\ Burnaby, B.C., Canada\\ goddyn@math.sfu.ca\\ \newpage \section{Introduction} A {\it homomorphism\/} from a graph $G$ into a graph $H$ is a mapping $f: V(G) \rightarrow V(H)$ such that $uv\in E(G)$ implies $f(u)f(v) \in E(H)$. If $G$ admits a homomorphism to $H$ we write $G \rightarrow H$. The {\it girth} of a graph $G$ is the minimum length of a circuit in $G$. The {\it odd girth} of a graph $G$ is the minimum length of an odd circuit in $G$. Both girth and odd girth can be viewed as measures of ``sparsity" in a graph. A {\it minor} of $G$ is any graph $H$ obtained from $G$ by contracting and deleting edges. A graph is {\it $H$-minor free} if it has no minor isomorphic to $H$. The {\it circular chromatic number} (sometimes called the ``star chromatic number'') of a graph $G$, denoted by $\chi_c(G)$, is the infimum of the set of real numbers $r$ for which there exists a map from $V(G)$ to the set of unit-length open arcs of a circle having circumference $r$, such that adjacent vertices map to disjoint arcs. It turns out that if we replace `circle' by `interval' (and `circumference' by `length') the resulting parameter is precisely the usual chromatic number $\chi(G)$; that the infimum in this definition can be achieved (and hence is the minimum); and that $\chi(G)=\lceil \chi_c(G) \rceil$; cf. the excellent survey article of X. Zhu \cite{Zhu3}. \noindent We investigate the connections between the properties of embeddability and sparsity of a graph and its (circular) chromatic number. The first result of this flavour is probably due to Gr\"otzsch \cite{Gro}, who proved that every planar graph with no triangle can be $3$-coloured. Some years later, Kronk and White \cite{KW} showed that every toroidal graph of girth at least $6$ can be $3$-coloured, while Cook \cite{Cook1} proved that if $G$ is a graph of genus $\gamma$ and the girth of $G$ is at least $\max\{9,6+2\log_2 (\gamma)\}$ then $G$ is $3$-colourable. Thomassen \cite{Thom1} improved this bound for toroidal graphs by showing that every toroidal graph of girth at least $5$ can be $3$-coloured. % Let $C_\ell$ denote a circuit of length $\ell$. A $3$-colouring of a graph $G$ is precisely a homomorphism to $C_3$. Thus we are lead to ask analogous questions about other odd circuits. % For instance we may ask: \begin{question}\label{hom-to-pentagon} Does there exist an integer $g_0$ such that any planar graph with girth at least $g_0$ admits a homomorphism to $C_5$? \end{question} An example by Albertson and Moore \cite{AlbMoo} (see Figure~\ref{AB-graph}) shows that if such an integer $g_0$ exists, then $g_0 \ge 8$. Jaeger's ``circular flow conjecture'' \cite{Jaeger} would imply that $g_0 \le 8$ suffices for the above question. It will follow from our results that answer is affirmative and that $g_0 \le 16$. \begin{figure}[htb] \begin{center} %\includegraphics{Homofig1.eps} %\epsfbox{9931-minor-free-girth-bipartite.fig1.eps} \centerline{\psfig{file=9931-minor-free-girth-bipartite.fig1.eps}} \caption{Albertson-Moore graph} \end{center} \label{AB-graph} \end{figure} We shall generalize these results to graphs of higher genus and to graphs avoiding a fixed minor. To this purpose we define two parameters. \begin{definition} Let $\ell$ be any odd integer greater than one, $\gamma$ any positive integer and $H$ any fixed graph. We define $g_{\gamma}({\ell})$ as the infimum of integers $g$ such that every graph $G$ of genus at most $\gamma$ and girth at least $g$ is homomorphic to $C_{\ell}$. We further define $g_{_{H}}({\ell})$ as the infimum of integers $g$ such that every $H$-minor free graph $G$ of girth at least $g$ is homomorphic to $C_{\ell}$. \end{definition} Thus $g_0(5)$ is the smallest value of $g_0$ which suffices for Question~1.1. We shall show that both the above parameters are finite and we give some explicit bounds on them in Sections 2, 3 and 4. Let ${\cal C}_\ell$ denote the class of all graphs $G$ with $G \rightarrow C_\ell$. It is easy to see that $${\cal C}_3 \supsetneq {\cal C}_5 \supsetneq {\cal C}_7 \supsetneq \cdots$$ and that $\bigcap{\cal C}_\ell$ is the class of bipartite graphs. %$$\bigcap_{\ell \mbox{ odd}} {\cal C}_\ell = {\cal B},$$ %where ${\cal B}$ is the class of all bipartite graphs. %Thus we may view graphs in ${\cal C}_\ell$, as $\ell$ increases, as being %closer and closer to being bipartite. Thus we view a graph in ${\cal C}_\ell$ ($\ell \gg 1$, $\ell$ odd) as being ``nearly bipartite'' %if it belongs to ${\cal C}_\ell$, with $\ell$ being a measure of the ``bipartiteness'' of the graph. This notion can be equivalently formulated in terms of circular chromatic numbers. \begin{proposition}\label{prop-equiv} For any graph $G$ and integer $k$, the following are equivalent: \begin{enumerate} \item $\chi_c(G) \le 2+\frac{1}{k}$ \item $G \rightarrow C_{2k+1}$ % \item There exists an orientation of $G$ such that for each circuit $C$ in $G$, % the proportion of edges of $C$ which are oriented in each direction % is at least $\frac{k}{2k+1}$. \end{enumerate} \end{proposition} %%%%%%%%%%%%%% % Thus a graph is ``nearly bipartite'' if its circular chromatic number is close to two. The subject of this paper is the study of classes of graphs for which high girth implies low circular chromatic number. Formally, we say that a class $\cal G$ of graphs is {\it girth-bipartite\/} if for any $\epsilon >0$ there exists an integer $g(\epsilon)$ such that every graph in $\cal G$ having girth at least $g(\epsilon)$ satisfies $\chi_c(G) \le 2+\epsilon$. %(We prefer the more descriptive term ``girth-bipartite'' since there are other variants of the intuitive notion of ``near bipartiteness''.) (We use term ``girth-bipartite'' to distinguish from other variants of the intuitive notion of ``near bipartiteness'' in the literature.) % The main result of this paper is the following. % %%%%%%%%%%%%%%%% \begin{theorem} \label{thm-minor} For every graph $H$, the class of $H$-minor free graphs is girth-bipartite. \end{theorem} %%%%%%%%%%%%%%%% % In particular, % {\it no minor-closed class of graphs whose members have unbounded girth can have its circular chromatic numbers bounded away from two. } % The condition that the graphs be $H$-minor free cannot be omitted, since there exist graphs having arbitrary girth and chromatic number. %%%%%%%%%%%%%%%%%%%%%% reference ! %%%%%%%%%%%%%%%%%%%%%%%%% A special case of Theorem \ref{thm-minor} concerns classes of graphs having bounded genus. In Theorem \ref{thm-genus} we give a specific upper bound on the circular chromatic number of graphs having a given girth and genus. The bound $g_0 \le 16$ mentioned above for the planar graphs is a special case of Theorem \ref{thm-genus}. The special case of Theorem \ref{thm-minor} where $H$ is planar was proved in 1996 by Ne\v{s}et\v{r}il and Zhu \cite[Corollary 2]{NesZhu}. In fact they prove something stronger, replacing the girth condition with a weaker hypothesis. The {\it odd girth\/} of a graph is the length of its shortest odd circuit (the odd girth of a bipartite graph is infinite). Consider the following three properties of a graph $G$ and integer $k$: \begin{description} \item[{\it P1:\/}] $G$ has girth at least $k$ \item[{\it P2:\/}] $G$ has a homomorphism into some graph having girth at least $k$ \item[{\it P3:\/}] $G$ has odd girth at least $k$. \end{description} % %%%%%%%%%%%%%%%% \begin{proposition} For any graph $G$ and any integer $k$, %property P1 implies property P2, and property P2 implies property P3. P1 implies P2, and P2 implies P3. \end{proposition} %%%%%%%%%%%%%%%% By considering $C_4$, and the Gr\"otzsch graph with $k=5$, we see that $P_2$ does not imply $P_1$ and $P_3$ does not imply $P_2$. % Hence, analogously to the definition of ``girth-bipartite'', we may define two stronger properties of a class $\cal G$ of graphs by replacing {\it P1\/} by {\it P2\/} (or {\it P3\/}) in the definition: %we say that $\cal G$ is {\it hom-girth-bipartite} ({\it odd-girth-bipartite}) if for some function $g(\epsilon)$ and all $\epsilon >0$, every graph in $\cal G$ satisfying {\it P2\/} ({\it P3\/}) with $k \ge g(\epsilon)$ satisfies $\chi_c(G) < 2+ \epsilon$. % When $H$ is planar, the $H$-minor free graphs have bounded {\it tree width\/} \cite{RS}. Thus we may state the Ne\v{s}et\v{r}il--Zhu result as follows. % %%%%%%%%%%%%%%%% %\begin{theorem}[{\protect\cite[Theorem 3]{NesZhu}}] \label{thm-hom-girth} \begin{theorem}\label{thm-hom-girth} Any class of graphs with bounded tree width is hom-girth-bipartite. \end{theorem} %%%%%%%%%%%%%%%% % This gives rise to a possible common generalization of the two results. % %%%%%%%%%%%%%%%% \begin{question} Is it true that for every graph $H$, the class of $H$-minor free graphs is hom-girth-bipartite? \end{question} %%%%%%%%%%%%%%%% % We do not know the answer here even in the special case of graphs of bounded genus. The above question has a negative answer if we replace ``hom-girth-bipartite'' with ``odd-girth-bipartite'' for there are projective planar graphs \cite{Youngs} with arbitrary odd girth and chromatic number 4. However, it is known \cite{Zhang} that the class of planar graphs is odd-girth-bipartite. Also it is proved in \cite{DGM} that for any orientable surface $\Sigma$ there exists an integer $r=r(\Sigma)$ such that the set of locally bipartite graphs embeddable on $\Sigma$ with representativity at least $r$ is odd-girth-bipartite. \medskip %Added by Luis% The concepts ``girth-bipartite'' and ``odd-girth-bipartite'' are easily dualized in the matroid sense. A {\it circulation\/} in a directed graph is a real-valued function on its arcs satisfying the usual flow-conservation law. The {\it circular flow number\/} of a graph $G=(V,E)$ is defined by $$ \phi_c(G) = \inf\{r\in\RR: \mbox{$G$ has an orientation $\vec{G}$ and a circulation $f:E(\vec{G})\rightarrow [1,r-1]$}\}. $$ For finite 2-edge connected graphs the infimum is attained at a rational number since for such graphs \cite{God} $$ \phi_c(G) = \min_{\vec{G}} \max_{X\se V} \;\; \frac {|\delta(X)|}{|\delta^+(X)|} $$ where the minimum is over all strong orientations of $G$. (Here $\delta^+(X)$ denotes the set of arcs in $\vec{G}$ with tails in $X$ and heads in $V-X$, and $\delta(X) = \delta^+(X) + \delta^+(V-X)$.) Analogously to chromatic numbers, the usual {\it flow number\/} of a graph $G$ \cite{God} is given by $\lceil \phi_c(G) \rceil$. %Dual to ``girth'' is ``cogirth''. The {\it cogirth\/} (resp.~{\it odd-cogirth\/}) of $G$ is the minimum size of a (odd-size) nonempty edge cut of $G$. By planar duality, our answer to Question \ref{hom-to-pentagon} is equivalent to the statement: any planar graph of cogirth at least 16 has circular flow number at most $\frac {5}{2}$. A class of graphs $\cal G$ is {\it cogirth-even} ({\it odd-cogirth-even}) if for some function $\lambda(\epsilon)$ and all $\epsilon >0$, every graph in $\cal G$ with cogirth (odd-cogirth) at least $\lambda(\epsilon)$ satisfies $\phi_c(G) < 2+ \epsilon$. In general, flow numbers behave better than chromatic numbers. For example, all bridgeless graphs $G$ satisfy $2\le\phi_c(G) \le 6$, and all graphs of cogirth at least four have $2\le \phi_c(G) \le 4$ \cite[p.297]{Sey-HoC}. Jaeger has proposed the following ``circular flow conjecture'' \cite{Jaeger}: %The second author has proposed the following \cite{God}. %%%%%%%%%%%%%% \begin{conjecture} The class of all graphs is {\it cogirth-even\/}. \end{conjecture} %%%%%%%%%%%%%% In fact, he proposes that $\lambda(1/k) = 4k$ suffices for integers $k \ge 1$. By planar duality, this would imply that $g_0(5)=\lambda(\frac {1}{2})=8$ suffices in Question~1.1. However, it is possible that a stronger statement holds. %%%%%%%%%%%%%% \begin{question} Is the class of all graphs odd-cogirth-even? \end{question} %%%%%%%%%%%%%% Zhang \cite{Zhang} has shown that any class of graphs of bounded genus is odd-cogirth-even, but little else is known about this problem. \section{Proof of Theorem \ref{thm-minor}} Our results rely on the simple observation that deleting a long induced path in a graph does not affect its circular chromatic number. That is, deleting the internal points of such a path from a graph will not change its circular chromatic number. % %%%%%%%%%%%%%%%%%%%%%% \begin{lemma} \label{lem-path} Let $P$ be an induced path of length $p$ in a graph $G$, let $U$ be the set of internal vertices of $P$, and let $\ell$ be any odd integer with $\ell \le p+1$. Then $G \rightarrow C_\ell$ if and only if $(G-U) \rightarrow C_\ell$ \end{lemma} %%%%%%%%%%%%%%%%%%%%%% % \begin{proof} The ``only if'' direction is trivial. Conversely, suppose that $\phi'$ is a homomorphism from $G-U$ into $C_\ell$. Let $x,y \in V(G)$ be the end-vertices of $P$. Since $\ell$ is odd and $p \ge \ell-1$, it is straightforward to check that, regardless of the values of $\phi'(x)$ and $\phi'(y)$, $\phi'$ can be extended to a homomorphism from $G$ into $C_\ell$. \end{proof} A graph $G$ is {\it $p$-path degenerate\/} if there is a sequence $G=G_0, G_1, \ldots, G_t$ of 2-connected subgraphs where $G_t$ is bipartite, and where each $G_i$ ($i>0$) is obtained by deleting from $G_{i-1}$ the internal vertices of an induced path of length at least $p$. By repeatedly applying Lemma \ref{lem-path} and observing that bipartite graphs have circular chromatic number $2$, we obtain the following. \begin{corollary} \label{cor-degen} If $G$ is $p$-path degenerate, then there is a homomorphism from $G$ into any odd circuit having length at most $p+1$, whence $\chi_c(G) \le 2 + \frac {1}{\lfloor\frac{p}{2}\rfloor}$. \end{corollary} Next, we show that every graph avoiding any fixed minor and having ``high enough" girth is $p$-path degenerate. For this, we rely on an observation of Thomassen \cite[p.~115]{TH3}. % %%%%%%%%%%%%%%%%%%%%%% \begin{lemma} \label{lem-thomassen} For any graph $H$ there exists an integer $k$ such that every $H$-minor free graph with minimum degree at least $3$ has girth at most $k$. \end{lemma} %%%%%%%%%%%%%%%%%%%%%% % \begin{definition} Let $k_H$ denote the least integer $k$ satisfying Lemma~\ref{lem-thomassen}. \end{definition} % %%%%%%%%%%%%%%%%%%%%%% \begin{lemma} \label{lem-H-degen} For any graph $H$ and integer $p$, every $H$-minor free graph with girth at least $(p-1)k_H+1$ is $p$-path degenerate. \end{lemma} %%%%%%%%%%%%%%%%%%%%%% % \begin{proof} Let $G$ be an $H$-minor free graph having girth at least $(p-1)k_H+1$. We claim that $G$ is $p$-path degenerate. We may assume that $G$ is $2$-connected since $G$ is $p$-path degenerate if each of its $2$-connected blocks is. If $G$ is a circuit, then this circuit has length at least $(p-1)k_H+1 \ge p+1$ and thus $G$ is $p$-path degenerate. Henceforth we assume that $G$ is a $2$-connected graph different from an edge or a circuit, and so there is a unique graph $G'$ with minimum degree at least $3$ which is homeomorphic to $G$. In other words, $G$ can be obtained from $G'$ by replacing each edge $e \in E(G')$ with a path $P(e)$ having length at least one. As $G'$ has no $H$-minor, $G$ has a circuit $C'$ of length at most $k_H$. The circuit $C$ in $G$ corresponding to $C'$ has length at least $(p-1)k_H+1$ so $C$ contains an induced path $P(e_0)$ having length at least $p$, for some $e_0 \in E(C')$. Deleting the internal vertices of $P(e_0)$ from $G$ leaves a smaller $H$-minor free graph with girth at least $(p-1)k_H+1$. By induction we have that $G$ is $p$-path degenerate. \end{proof} {\sc Proof of Theorem \ref{thm-minor}.~~} The result follows immediately from Corollary \ref{cor-degen} and Lemma \ref{lem-H-degen}. \hfill $\Box$\par\medskip% Indeed we have that every $H$-minor free graph $G$ with girth at least $(p-1)k_H+1$ has a homomorphism onto any odd circuit of length $\ell \le p+1$, and thus $\chi_c(G) \le 2+\frac {1}{\lfloor \frac{p}{2} \rfloor}$. An upper bound for $\chi_c(G)$, is obtained by choosing $p$ as large as possible in Lemma~\ref{lem-H-degen}. Thus: % %%%% % \begin{corollary}\label{thm-ineq} For any $H$-minor free graph $G$ of girth $g$ $$G \rightarrow C_\ell\quad \mbox { for any odd integer $\ell \le \frac{g - 1}{k_H} + 2$ }.$$ \end{corollary} % %%%% % Determining $k_H$ is difficult in general, however, in the following, we provide an upper bound on it when $H=K_t$. Mader \cite{Mader} (see \cite[p.~333]{Tho-HoC} for an English language version) proved that: %%%%%%%%%%%%%%%%%%%%%% \begin{lemma} \label{lem-mader} For each positive integer $t$ there exists an integer $d(t)$ such that every simple graph with minimum degree at least $d(t)$ contains $K_t$ as a minor. \end{lemma} %%%%%%%%%%%%%%%%%%%%%% % Later, Kostochka \cite{Kosto} showed that any simple graph with average degree at least $2t$ has a $K_{\eta}$-minor where $\eta\ge .064t/ \sqrt{\log_2 t}$. This implies $d(t) = 66t \sqrt{\log_2 t}$ suffices in Lemma \ref{lem-mader} for $t \ge 3$. Finally, Thomason \cite{Thomason} proved that the constant $66$ may be lowered to $5.36$ if $t$ is large. % \begin{lemma} \label{thm-kosto} If $H=K_{t}$, $t\ge 3$, then $k_H< 4c_1t \sqrt {\log_2 t}$, where $c_1=66$. \end{lemma} \begin{proof} Consider a graph $G$ with minimum degree at least $3$ and girth at least $4c_1t \sqrt {\log_2 t}$. By Thomassen's proof of Lemma \ref{lem-thomassen}, $G$ contains as a minor a simple subgraph $F$ whose minimum degree $\delta(F)$ is at least $c_1t\sqrt {\log_2 t}$. Hence by the remark following Lemma \ref{lem-mader}, there exists a $K_t$-minor in $G$. \end{proof} % For any simple graph $H$ of order $t$, the above lemma yields an upper bound for $k_H$ depending only on $t$ and on the girth of $G$. Thus, by replacing this bound into the formula in Corollary~\ref{thm-ineq}, we get the following bound for the smallest girth which ensures that any $H$-minor free graph admits a homomorphism to $C_{\ell}$: \begin{corollary} Let $H$ be a fixed graph of order $t$ and let $\ell>1$ be an odd integer. Then, $$g_{_{H}}(\ell) \;\;\le\;\; 264(\ell-2)t\sqrt{\log_2 t}+1.$$ \end{corollary} Finding better upper bounds on $g_{_{H}}(\ell)$ for specific forbidden minors $H$ is the topic of Section~4. It is worth noticing that a result analougous to Lemma~\ref{lem-mader} holds true \cite {BT} when $K_t$ is contained as a {\em topological minor}, i.e., a subgraph isomorphic to a subdivision of $K_t$. All results in this paper may be stated in this setting, including our main theorem: \begin{theorem} \label{thm-top-minor} For every graph $H$, the class of graphs which do not contain $H$ as a topological minor is girth-bipartite. \end{theorem} % % % \section{Graphs of bounded genus} The (orientable) {\it genus\/} of a graph $G$ is the mimimum number of ``handles'' which must be added to a sphere in order to obtain a surface into which $G$ has an embedding. Thus planar graphs have genus zero. We refer the reader to \cite{Tho-HoC} for further details on graph embeddings. All graphs of genus at most $\gamma$ are $H$-minor free for any graph $H$ having genus greater than $\gamma$. Thus any class of graphs of bounded genus is girth-bipartite. In this section we specialize the bounds of the previous section to graphs having bounded genus. % %%% % \begin{definition} Let $k_\gamma$ denote the least integer such that all graphs with genus at most $\gamma$ with minimum degree at least $3$ have girth at most $k_\gamma$. \end{definition} For example, it is well known that $k_0 = 5$ and $k_1 = 7$. By exactly the same argument as the proof of Lemma \ref{lem-H-degen}, any graph of genus at most $\gamma$ and girth at least $(p-1)k_\gamma+1$ is $p$-path degenerate. Thus any graph of genus at most $\gamma$ satisfies the inequalities of Theorem \ref{thm-ineq} with $k_H$ replaced by $k_\gamma$. The goal of this section is to derive the following upper bound on $k_\gamma$. % %%%%%%%% % \begin{theorem}\label{thm-genus} For any $\gamma \ge 0$, we have \begin{equation} \label{eqn-maxgirth} k_\gamma \le 4 + \lfloor 2 \log_2 (\gamma+3/2) \rfloor. \end{equation} \end{theorem} % %%%%%%%% % \begin{corollary}\label{cor-genus} For any graph $G$ of girth $g$ and genus at most $\gamma$, \begin{enumerate} \item $G \rightarrow C_\ell$ for any odd integer $\ell \le 2+\frac{g -1}{4+\lfloor 2\log_2(\gamma+3/2)\rfloor}$; \item $g_{\gamma}(\ell)\le (\ell-2)(4+\lfloor 2 \log_2 (\gamma+3/2) \rfloor)+1.$ \end{enumerate} \end{corollary} % %%%%%%%% % %We define a function %\begin{equation} \label{eqn-maxgirth} %h(\gamma) := 4 + \lfloor 2 \log_2 (\gamma+3/2) \rfloor. %\end{equation} % % %The main result for graphs follows. %\begin{theorem}\label{thm-genus} %If $G$ has girth at least $g$ and genus at most $\gamma$, then %$$ %\chi_c(G) %%\le 2+ \frac{2}{\lceil\frac{g-h(\gamma)}{h(\gamma)}\rceil} %\le 2+ \frac{2}{\lceil\frac{g}{h(\gamma)}-1\rceil} %\le \frac{2g}{g-2\log_2(4\gamma+6)}\;. %$$ %\end{theorem} In particular, any planar graph with girth at least $16$ has a homomorphism into a pentagon, which answers Question~1.1. We note here that the dependence on genus arises only through Euler's characteristic formula. Thus a similar formula holds regarding the unoriented genus of $G$: if $G$ embeds on $N_{\gamma'}$, the sphere with $\gamma'$ crosscaps, then conclusion of Corollary \ref{cor-genus} holds upon substituting $2\gamma'$ for $\gamma$. %\section{The Proof} A {\it $(g,k)$-cage\/} is a graph having minimum degree at least $k$ and girth at least $g$ with the fewest possible number of vertices. There is a well-known lower bound (see \cite{Bol}) for the number $n(g,k)$ of vertices in a $(g,k)$-cage. In particular, \begin{equation} \label{eqn-cagebound} n(g,3) \ge \left\{ \begin{array}{ll} 2 \cdot 2^{g/2}-2 & \mbox{if $g$ is even}\\ 3 \cdot 2^{(g-1)/2} & \mbox{if $g$ is odd} \end{array}\right\} \ge 2 \cdot 2^{g/2}-2. \end{equation} %%%%%%%%%%%%% \begin{lemma}\label{lem-genus} If $G$ is a graph having minimum degree at least $3$, girth $g \ge 6$ and genus $\gamma$, then %$G$ has genus at least \begin{equation} \label{eqn-mingenus} \gamma \ge 1+\lceil \frac{g-6}{4g} n(g,3) \rceil . \end{equation} \end{lemma} \begin{proof} Let $G$ be a graph with $n$ vertices, $e$ edges, girth $g$, genus $\gamma$ and minimum degree at least $3$. If $g=6$, then $G$ is not planar and we are done, so we may assume $g \ge 7$. Suppose $G$ has $r$ regions when embedded onto $S_{\gamma}$. We follow Cook's argument in \cite{Cook} which uses Euler's formula and the inequalities $gr \le 2e \le 3n$ to derive $$ n \le \frac{4 g (\gamma-1)}{g-6}. $$ On the other hand we have by definition of a cage, $n \ge n(g,3)$. The two inequalities imply (\ref{eqn-mingenus}). \end{proof} %%%%%%%%%%%% %%%%%%%% \vspace{1ex} \noindent {\sc Proof of Theorem \ref{thm-genus}.~~} Let $G$ be a graph having minimum degree at least $3$ and genus $\gamma$. Let $h(\gamma)$ be the function expressed in the right hand side of (\ref{eqn-maxgirth}). Our goal is to show that the girth $g$ of $G$ is smaller than or equal to $h(\gamma)$. We have $h(0)=5$, $h(1)=7$ which are well known upper bounds for planar and toroidal graphs. We may assume %$G$ has minimum degree $\ge 3$, genus $\gamma \ge 2$ and girth $g\ge 7$. that $G$ has genus $\gamma \ge 2$ and apply Lemma \ref{lem-genus}. From (\ref{eqn-cagebound}) and (\ref{eqn-mingenus}) we have % \begin{equation} \label{eqn-lowbound} %\gamma \ge 1 + \frac{1}{4} (1-\frac{6}{g}) ( 2\cdot 2^{g/2}-2 ) . \gamma \ge 1 + \frac{1}{2} (1-\frac{6}{g}) ( 2^{g/2}-1 ) . \end{equation} % If $7 \le g \le 11$, then we verify the corollary numerically by checking that $g \le h(\gamma)$ when the right hand side of (\ref{eqn-lowbound}) is substituted for $\gamma$. % If $g \ge 12$, then we have from (\ref{eqn-lowbound}) $$ 4(\gamma + \frac {3}{2}) \ge 4+ (2^{g/2}+2^{g/2}-2) - \frac{12}{g}(2^{g/2}-1) + 6 > 2^{g/2} $$ and the result follows by taking logarithms. \hfill $\Box$\par\medskip% %%%%%%%%%%%%%%%%%%%%%%%%%%% The upper bound (\ref{eqn-maxgirth}) compares quite well to the best upper bound to $k_\gamma$ that can be possibly be derived from (\ref{eqn-mingenus}) and the first inequality in (\ref{eqn-cagebound}). In fact, the two bounds are equal for $\gamma \le 7$, they differ by at most one when $\gamma \le 11$, and they never differ by more than two. The exact value of $k_\gamma$ appears to be very difficult to determine. The best upper bound to $g_{\gamma}(\ell)$ in terms of the girth and genus of $G$ appears to be extremely hard to determine, even for planar graphs. %Gary McGillivray (personal communication) has shown that every planar graph %having girth at least $15$ has a homomorphism onto a pentagon, %which improves the bound of Corollary \ref{cor-genus} by one. %%%%%%%%%%%%%%% \section{Bounds for specific forbidden minors $H$} The bound defined in the previous sections can be improved in case specific minors are forbidden. This problem has been considered by Hell and Zhu \cite{HZ} for the class of series-parallel graphs. They proved that any series-parallel graph $G$ of girth at least $2\lfloor (3k-1)/2\rfloor$ is homomorphic to $C_{2k-1}$. Since each 2-connected component of a $K_4$-minor free graph is a series-parallel graph, the same bound holds for the class of $K_4$-minor free graphs, i.e., $g_{_{K_4}}(\ell) \le \frac {3 {\ell}+1}{2}$. It was pointed out by Gerards \cite{Ger} that the subdivisions of $K_4$ play an important role in homomorphisms to odd circuits. An odd-$K_4$ and an odd-$K_3^2$ are shown in Fig.~\ref{Odd}, where the word ``odd" inside a face means that the length of that face is odd. \begin{figure}[htb] \begin{center} \centerline{\epsfbox{9931-minor-free-girth-bipartite.fig2.eps}} \caption{a) Odd-$K_4$, b) Odd-$K_3^2$} \end{center} \label{Odd} \end{figure} \bigskip In fact, he proved \cite{Ger} that: \begin{theorem} \label{Gerards} Let $G$ be a nonbipartite graph. If $G$ contains neither an odd-$K_4$ nor an odd-$K^2_3$ then $G$ admits a homomorphism onto its shortest odd circuit. \end{theorem} Clearly, an odd-$K^2_3$ contains as a $K^2_3$ as a minor (where $K^2_3$ is a $K_3$ with all edges doubled). On the other hand, $K^2_3$-minor free graphs may contain an odd-$K_4$-minor, and hence, constitute a non trivial class where to consider homomorphisms to odd circuit. By dualizing the characterization of Seymour \cite{Sey} of $K_{2,3}$-minor free graphs, we may state the following: \begin{theorem} \label{MinorK} Let $G$ be a 2-connected $K^2_3$-minor free graph. Then either $G$ does not contain a $K_4$-minor or $G$ is a subdivision of a $K_4$. \end{theorem} \bigskip By the above theorem and Gerards' theorem, we expect that odd-$K_4$'s are obstructions to finding homomorphisms onto odd circuits. The next lemma confirms this. We denote by $x_1,x_2,x_3,x_4$ the vertices of degree three in the $K_4$ subdivision and we call {\it arms} the paths $[x_i,x_j]$ joining different pairs $x_i$, $x_j$, $1\le i,j\le 4$. \begin{lemma} Let $G$ be an odd-$K_4$ of girth $3k$. If all arms have length $k$ then $G$ is not homomorphic to $C_{2k+1}$. \end{lemma} \begin{proof} Let $V(C_{2k+1})=\{0,1,\dots,2k\}$. Suppose there exists a homomorphism $\phi$ from $G$ onto $C_{2k+1}$. We may assume without loss of generality that $x_1$ receives colour $0$, namely $\phi(x_1)=0$. Now, we distinguish two cases: either both the vertices $x_2$ and $x_3$ receive an even colour or they both receive an odd colour. In the first case, since the lengths of the paths between $x_1$ and $x_2$, and, $x_1$ and $x_3$ respectively, are odd and equal to $k$, it follows that the $\phi(x_2)$ and $\phi(x_3)$ must be at least $k+1$. This implies that the circuit $[x_1,x_2]\cup [x_2,x_3]\cup [x_3,x_1]$ cannot be mapped onto $C_{2k+1}$. Similarly, if the labels of $x_2$ and $x_3$ are both odd, they must have value smaller than or equal to $k$ which again implies that the circuit $[x_1,x_2]\cup [x_2,x_3]\cup [x_3,x_1]$ cannot be mapped onto $C_{2k+1}$. \end{proof} \bigskip Now we show that any odd-$K_4$, regardless from the length of its arms, of girth at least $3k$ can be mapped onto $C_{2k-1}$. To prove this, we introduce the operation of {\it folding}, i.e., identification of two nonadjacent vertices having a common neighbour. \begin{lemma} \label{bound} Let $G$ be an odd-$K_4$ of girth $\ge 3k$. Then $G$ is homomorphic to $C_{2k-1}$. \end{lemma} \begin{proof} It is enough to prove the thesis when $G$ has girth $3k$. First of all observe that at least one of the arms of $K_4$ has length smaller than or equal to $k$, since otherwise the girth of $G$ would be greater than $3k$. We may assume without loss of generality that the arm $[x_1,x_2]$ has length $l\le k$. If $l$ is even then we fold the arm $[x_1,x_2]$ $l/2$ times. If $l$ is odd then we fold the arm $(l-1)/2$ times, thus obtaining an arm of length 1. Then, we fold this remaining edge with the first edge of the arm $[x_1,x_4]$. In each case, the resulting graph has girth at least $2k-1$ and contains neither an odd-$K_4$ nor an odd-$K^2_3$. Hence, by Theorem~\ref{Gerards}, it is homomorphic to its shortest odd circuit, which has length at least $2k-1$, and hence also to $C_{2k-1}$. \end{proof} It follows easily from Theorems~\ref{MinorK}, \ref{Gerards} and Lemma~\ref{bound} that: \begin{theorem} \label{3k} Let $\ell>1$ be an odd integer. Then, $$g_{_{K^2_3}}(\ell)\le \frac {3(\ell +1)}{2}.$$ % of girth $g(G)$. If $g(G)\ge 3k$ then %$G$ is homomorphic to $C_{2k-1}$. \end{theorem} \bigskip Note that if $F$ is a minor of $H$ then the bound for $F$-minor free graphs is at most the bound obtained for $H$-minor free graphs. It follows that if $H$ is a minor of $K_4$ or a minor of $K^2_3$ and $G$ is an $H$-minor free graph, then $G$ is homomorphic to $C_{2k+1}$ provided that the girth of $G$ is at least $3(k+1)$. Observe also that if $H$ is a minor of both $K_4$ and $K^2_3$ and $G$ is $H$-minor free then $G$ is homomorphic to $C_{2k+1}$ provided that the girth of $G$ is at least $2k+1$, by Gerards' theorem. \bigskip \bibliographystyle{plain} \bibliography{9931-minor-free-girth-bipartite} \end{document}