% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P3.7}{22(3)}{2015} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsfonts,amssymb,amsmath,titling,cancel,color,amsthm} \usepackage{verbatim,tikz} \usepackage{epstopdf} \usepackage{graphicx} \usepackage{pifont} \usepackage{color} \usepackage{tkz-graph} \usepackage{float} \restylefloat{figure} %\usepackage{hyperref} % we recommend the graphicx package for importing figures %\usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \allowdisplaybreaks % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Acyclic Subgraphs of Planar Digraphs} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Noah Golowich\\ \small Research Science Institute\\[-0.8ex] \small Department of Mathematics\\[-0.8ex] \small Massachusetts Institute of Technology\\[-0.8ex] \small Cambridge, Massachusetts, U.S.A.\\ \small\tt ngolowich@college.harvard.edu\\ \and David Rolnick\\ \small Department of Mathematics\\[-0.8ex] \small Massachusetts Institute of Technology\\[-0.8ex] \small Cambridge, Massachusetts, U.S.A.\\ \small\tt drolnick@mit.edu } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Aug 11, 2014}{Jun 18, 2015}{Jul 1, 2015}\\ \small Mathematics Subject Classifications: 05C10, 05C15} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} An acyclic set in a digraph is a set of vertices that induces an acyclic subgraph. In 2011, Harutyunyan conjectured that every planar digraph on $n$ vertices without directed 2-cycles possesses an acyclic set of size at least $3n/5$. We prove this conjecture for digraphs where every directed cycle has length at least 8. More generally, if $g$ is the length of the shortest directed cycle, we show that there exists an acyclic set of size at least $(1 - 3/g)n$. % keywords are optional \bigskip\noindent \textbf{Keywords:} acyclic set, chromatic number, digraph, planar graph, directed cut \end{abstract} \section{Introduction} A proper {\it vertex coloring} of an undirected graph $G$ partitions the vertices into independent sets. It is natural to try to reformulate this notion for directed graphs (digraphs). An {\it acyclic set} in a digraph is a set of vertices whose induced subgraph contains no directed cycle. The {\it digraph chromatic number} of a digraph $D$, denoted $\chi_A(D)$, is the minimal number of acyclic sets into which the vertices of $D$ may be partitioned. In this paper, we consider \emph{oriented graphs}, which are digraphs such that at most one arc connects any pair of vertices. Although recent results \cite{acyclic_aharoni_2008, circular_bokal_2004, two_harut_2012, digraph_keevash_2013} suggest that the digraph chromatic number behaves similarly to the undirected chromatic number, much still remains to be learned. For instance, Neumann-Lara conjectured that all oriented planar graphs have digraph chromatic number at most 2. \begin{conjecture}[\cite{vertex_neumann_1985}] \label{conj:skrekovski} Every oriented planar graph is digraph 2-colorable. \end{conjecture} The fact that Conjecture \ref{conj:skrekovski} holds if one allows three colors instead of two is well-known and is an immediate consequence of 5-degeneracy of planar graphs (see, for instance \cite{circular_bokal_2004}). %Bokal et al.~\cite{circular_bokal_2004} observed that all oriented planar graphs are acyclically 3-colorable. One approach to Conjecture \ref{conj:skrekovski} has been to look for lower bounds on the size of the largest acyclic set of a planar oriented graph. Borodin \cite{borodin_acyclic_1979} showed that in any undirected planar graph there exists an induced forest of size $2n/5$, where $n$ denotes the number of vertices of the graph. This result implies that there must exist an acyclic set of size at least $2n/5$ in any oriented planar graph. Albertson and Berman \cite{albertson_conjecture_1979} moreover conjectured that every undirected planar graph has an induced forest of size at least $n/2$, which would imply that every oriented planar graph has an acyclic set of size $n/2$. %Note that this would follow immediately from Conjecture \ref{conj:skrekovski}. %Albertson \cite{albertson_problems_2002} has also suggested an easier problem than Conjecture \ref{conj:skrekovski}: %\begin{conjecture}[Albertson, 2002] %\label{conj:albertson} %Every oriented planar graph contains a subset of at least half its vertices which induces an acyclic subgraph. %\end{conjecture} %If Conjecture \ref{conj:skrekovski} were true, then Conjecture \ref{conj:albertson} would follow immediately. Harutyunyan and Mohar \cite{harut_planar_2014} recently conjectured an even stronger bound on the maximum size of an acyclic set, which, if true, would be tight: \begin{conjecture}[\cite{harut_planar_2014}] %What is the correct citation for this? \label{conj:harut} Every oriented planar graph on $n$ vertices contains an acyclic set of size at least $3n/5$. \end{conjecture} Finding the largest size of an acyclic set in a digraph is equivalent to finding a set of vertices of minimum size which has a non-empty intersection with each directed cycle. In \cite{generalized_jain_2005}, Jain et al. investigated the applications of this problem in deadlock resolution. The {\it digirth} of a directed graph is the length of its shortest directed cycle. Fox and Pach \cite{fox_separator_2010} considered how many vertices must be removed from an undirected graph $G$ to yield a forest, where $G$ belongs to a hereditary family of graphs with small separators (such as the family of planar graphs). Their approach also applies to the directed case and shows that in an oriented planar graph there is always an acyclic set of size $(1 - c/\sqrt{g})n$, where $c$ is an absolute constant and $g$ is the digirth. Recently, Harutyunyan and Mohar \cite{harut_planar_2014} proved that every oriented planar graph of digirth at least 5 is digraph 2-colorable, and therefore contains an acyclic set of size at least $n/2$. They used an intricate vertex-discharging method to show that any minimal counterexample must contain at least one of 25 specific configurations of vertices and arcs. %They then demonstrated that if a digraph contains one of these configurations, the problem of finding an acyclic 2-coloring of the digraph reduces to finding an acyclic 2-coloring of a digraph with one fewer vertex, thus showing that no minimal counterexample exists. The authors posed the problem of finding a simpler approach for considering digraph colorings in oriented planar graphs. In this paper, we introduce such an approach to prove Theorem \ref{thm:main}, which improves known lower bounds on the largest acyclic set in oriented planar graphs of digirth at least 4. Specifically, we give a short proof of the fact that every oriented planar graph on $n$ vertices and of digirth $g$ possesses an acyclic set of size at least $(1-3/g)n$, thus proving Conjecture \ref{conj:harut} when $g \geq 8$. We also give a slightly stronger bound for the cases $g = 4$ and $g=5$. We prove Theorem \ref{thm:main} by using a corollary of the Lucchesi-Younger theorem \cite{lucchesi_minimax_1978} to find an upper bound on the size of the minimum feedback arc set of an oriented planar graph. In Section \ref{sec:proof}, we prove our main result, Theorem \ref{thm:main}. In Section \ref{sec:counter}, we describe some potential extensions of Theorem \ref{thm:main} and difficulties that arise. \section{Bounds on the largest acyclic set} \label{sec:proof} In this section, we use a corollary of the Lucchesi-Younger theorem to prove Theorem \ref{thm:main}. We begin with some definitions. Given a directed graph $D$ and a subset $X$ of its vertices $V(D)$, we define $\bar{X} = V(D) \backslash X$. If every arc between $X$ and $\bar{X}$ is directed from $X$ to $\bar{X}$, then the set of such arcs is called a {\it directed cut}. A {\it dijoin} is a set of arcs that has a non-empty intersection with every directed cut. The Lucchesi-Younger theorem \cite{lucchesi_minimax_1978} gives the minimum size of a dijoin of a digraph: \begin{theorem}[Lucchesi-Younger \cite{lucchesi_minimax_1978}] The minimum cardinality of a dijoin in a directed graph $D$ is equal to the maximum number of pairwise disjoint directed cuts of $D$. \end{theorem} In the case that $D$ is planar, the Lucchesi-Younger theorem has a useful corollary for the dual of $D$. Given an oriented planar graph $D$, the {\it dual} of $D$, denoted $D^{\star}$, is defined as follows. For a given planar embedding of $D$, construct a vertex of $D^\star$ within each face of $D$. For each arc $uv$ of $D$ separating faces $f$ and $g$ of $D$, a corresponding arc $f^\star g^\star\in A(D^\star)$ is drawn between vertices $f^\star$ and $g^\star$. The direction of arc $f^\star g^\star$ is defined so that as it crosses $uv$, $v$ is on the left. It is simple to verify that the graph $D^\star$ does not depend on the planar embedding of $D$. The following well-known result establishes a bijection between the directed cycles of an oriented planar graph and the directed cuts in its dual: %\cite{not_sure_what_to_cite} \begin{proposition} \label{prop:bij} If $D$ is an oriented planar graph, then the directed cycles of $D$ are in one-to-one correspondence with the directed cuts in $D^\star$. \end{proposition} \begin{proof} Pick a planar embedding of $D$ and then embed $D^\star$ in the plane as defined above. Given a directed cycle $C$ in $D$, notice that all arcs of $D^\star$ crossing an arc of $C$ must travel in the same direction: specifically, if $C$ is oriented clockwise, then all arcs of $D^\star$ crossing $C$ point inwards, and if $C$ is oriented counterclockwise, then the arcs of $D^\star$ crossing $C$ point outwards. Let $X \subset V(D^\star)$ consist of the vertices of $D^\star$ corresponding to all faces of $D$ inside $C$, and therefore the arcs of $D^\star$ connecting $X$ and $V(D^\star) \backslash X$ form a directed cut. Conversely, given a directed cut of $V(D^\star)$, we reverse the method above to obtain a directed cycle of $D$. \end{proof} Given a directed graph, a {\it feedback arc set} is a set of arcs, the removal of which eliminates all directed cycles. We will be concerned with \emph{minimum feedback arc sets}, namely those of minimum cardinality. Proposition $\ref{prop:bij}$ establishes the following corollary of the Lucchesi-Younger theorem: \begin{corollary}[\cite{lucchesi_minimax_1978}] \label{cor:lucchesi} For an oriented planar graph, the minimum size of a feedback arc set is equal to the maximum number of arc-disjoint directed cycles. \end{corollary} \begin{proof} Given an oriented planar graph $D$, by the Lucchesi-Younger theorem, the minimum cardinality of a dijoin of $D^\star$ is equal to the maximum number of disjoint directed cuts of $D^\star$. Now, by Proposition $\ref{prop:bij}$, any dijoin of $D^\star$ corresponds to a unique feedback arc set of $D$ of the same size, and any set of disjoint directed cuts of $D^\star$ corresponds to a unique set of arc-disjoint directed cycles of $D$, also of the same size. This completes the proof. \end{proof} We also need one well-known lemma, which follows easily from Euler's formula for planar graphs. \begin{lemma} \label{lem:mn} Any planar graph $G$ with $n$ vertices and $m$ arcs satisfies $m \leq 3n - 6$. \end{lemma} We now are ready to state and prove our main theorem. \begin{theorem} \label{thm:main} If $D$ is an oriented planar graph with digirth $g$ on $n$ vertices, then there exists an acyclic set in $D$ of size at least $n - 3n/g$. Moreover, if $g = 4$, there exists an acyclic set of size at least $5n/12$, and if $g = 5$, there exists an acyclic set of size at least $7n/15$. \end{theorem} \begin{proof} A \emph{vertex cover} of a given arc set $A$ is a set $S$ of vertices for which every arc in $A$ is incident to some vertex in $S$. Observe that if $S$ is a vertex cover of a feedback arc set in a digraph $D$, then the complement of $S$ in $V(D)$ is an acyclic set. This is because every directed cycle must include an element of the feedback arc set. Given an oriented planar graph $D$ of digirth $g$, let $H$ be a collection of arc-disjoint directed cycles, each of which must have length at least $g$. Thus, by Lemma \ref{lem:mn} the number of cycles in $H$ is at most $a(D)/g \leq 3n/g$, where $a(D)$ denotes the number of arcs of $D$. Corollary \ref{cor:lucchesi} implies that there exists a feedback arc set with cardinality at most $3n/g$. Removing a vertex cover of this feedback arc set, we are left with an acyclic set of at least $n - 3n/g$ vertices. %\begin{theorem} %On a planar digraph of girth 4, there is an acyclic set of $5n/12$ vertices, and on a planar digraph of girth 5, there is an acyclic set of $8n/15$ vertices. %\end{theorem} For the cases $g = 4,5$, we now derive a better bound by using the greedy algorithm to obtain a smaller vertex cover of the feedback arc set. This is possible because $3n/g > n/2$, meaning that some vertices are incident to 2 or more feedback arcs. Suppose that our feedback arc set consists initially of $f$ arcs, where $f\le 3n/g$. Let $d$ equal the number of feedback arcs minus half the number of vertices. Thus, initially $d=f-n/2$. At each step, we remove the vertex $v$ that is incident to the most feedback arcs, together with all feedback arcs incident to $v$. As long as $d>0$, each step removes one vertex and at least two feedback arcs. Such a step decreases $d$ by at least $3/2$. Let $m$ be the number of steps taken before $d\le 0$, and let $d'\le 0$ be the final value of $d$. We conclude that $$m\le \frac{f-n/2-d'}{3/2}=\frac{2f-n-2d'}{3}.$$ After $m$ steps, the number of vertices remaining is $n-m$, so the number of feedback arcs remaining is $d'+(n-m)/2$. We remove one vertex from each of these feedback arcs so that the vertices remaining at the end form an acyclic set. The total number of vertices removed is \begin{align*} m+d'+\frac{n-m}{2} %=\frac{n}{2}+d'+\frac{m}{2}%\\ & CSG \, \le \, \frac{n}{2}+d'+\frac{1}{2}\cdot \frac{2f-n-2d'}{3} %CSG\\ \, &=\, \frac{n+f+2d'}{3}\\ &\le\, \frac{n+f}{3} %\\ &\le CSG \, \le \, \frac{n}{3}+\frac{n}{g}. \end{align*} The number of vertices remaining in our acyclic set is thus at least$$\frac{2n}{3}-\frac{n}{g}.$$ This is equal to $5n/12$ for $g=4$ and $7n/15$ for $g=5$. % Another way: % Suppose we remove $f_i \geq 2$ vertices at each step. Then the number of steps is exactly the smallest integer $m$ such that there is a positive real number $D$ such that % \begin{equation} % \label{eq:nm} % D + \frac{3n}{g} - \sum_{i = 1}^m f_i = \frac{n-m}{2}. % \end{equation} % Now, the total number of vertices we need to cover all the feedback edges is $m + 3n/g - \sum_{i = 1}^m f_i$. By $(\ref{eq:nm})$, this number of vertices is at most $\frac{n+m}{2} - D$. % if equality holds in (\ref{eq:nm}), and $\frac{n+m}{2} - \frac{1}{2}$ otherwise. % Now, we let $f' = \frac{ \sum_{i = 1}^m f_i}{m}$, meaning that $f' \geq 2$. Thus, we can rewrite (\ref{eq:nm}) as % \begin{equation} % m\left(f' - \frac{1}{2}\right) = n \left( \frac{6-g}{2g} \right) - D\nonumber % \end{equation} % Since $m$ is the smallest integer such that there exists $D>0$ so that the above is satisfied, we have % \begin{equation} % m = \frac{n\left(\frac{6-g}{2g}\right) - D}{f' - \frac{1}{2}} \leq \frac{n\left(\frac{6-g}{2g}\right)}{f' - \frac{1}{2}}\nonumber, % \end{equation} % and since $f' - 1/2 \geq 3/2$, we have that $m \leq n(6-g)/(3g).$ Thus, the maximum set of vertices remaining is of size at least % \begin{equation} % \frac{2n}{3} - \frac{n}{g}\nonumber. % \end{equation} \end{proof} Note that our result for $g = 5$ and $g = 6$ is already known; in fact, as mentioned before, the main result of \cite{harut_planar_2014} implies the existence of an acyclic set of size at least $n/2$ for $g \geq 5$. %The fact that there is an acyclic set of size at least $n/2$ when $g = 6$ is already known \cite{harut_planar_2014}, as is a bound of $n/2$ when $g = 5$ \cite{harut_planar_2014}. However, our bound of $5n/12$ improves all previous results for $g = 4$ and our bound of $n - 3n/g$ improves all previous results for $g \geq 7$. \section{Further directions} \label{sec:counter} In this section we describe methods that might be used to strengthen our main result, and difficulties that arise. \subsection{Digraph 2-colorings} Harutyunyan and Mohar \cite{harut_planar_2014} asked whether there is a simple proof of the fact that oriented planar graphs of large digirth are digraph 2-colorable. We showed above that we can find a very large acyclic set in an oriented planar graph of large digirth. It is natural to ask whether, given a minimum feedback arc set as in Theorem \ref{thm:main}, we can choose a vertex cover $Y$ of the feedback arc set such that $Y$ induces an acyclic subgraph. This would imply that oriented planar graphs of large digirth are digraph 2-colorable, because the subgraph induced by $V(D) \backslash Y$ contains no feedback arcs and hence is acyclic. We now show that there are oriented planar graphs for which no such $Y$ can be found. \begin{proposition} \label{prop:bigraph} There exists an oriented planar graph $D$ such that, for any minimum feedback arc set $F$ of $D$, and for any vertex cover $Y$ of $F$, there is a directed cycle in the subgraph induced by $Y$. \end{proposition} \begin{proof} We show that the digraph $D$ in Figure \ref{fig:bigraph} satisfies the necessary conditions. The unique minimum feedback arc set $\{ab, bc, ac, ed, gf, hi\}$ is indicated with dashed lines. Notice that any vertex cover of the minimum feedback arc set must contain at least 2 vertices from the central triangle $abc$, suppose $a$ and $b$ without loss of generality. We must now choose either $d$ or $e$ to cover arc $de$. However, if we choose $d$, then $abd$ is a directed 3-cycle, and if we choose $e$, then $abe$ is a directed 3-cycle. This completes the proof. \end{proof} \begin{figure}[ht!] \SetVertexNormal[Shape = circle, FillColor = white, LineWidth = .5pt] \SetUpEdge[lw = 1.3pt, color = black, labelcolor = white, labeltext = red, labelstyle = {sloped,draw,text=blue}] \begin{center} \begin{tikzpicture} \tikzset{VertexStyle/.style = {shape = circle,fill = pink,minimum size = 2pt,inner sep = 2.5pt}} \Vertex[x=-1.5 ,y=0]{a} \Vertex[x=1.5,y=0]{b} \Vertex[x=0,y=2.6]{c} \Vertex[x=-1.5,y=-4]{d} \Vertex[x=1.5,y=-4]{e} \Vertex[x=4.96,y=2]{f} \Vertex[x=3.4,y=4.6]{g} \Vertex[x=-3.4,y=4.6]{h} \Vertex[x=-4.96,y=2]{i} \Vertex[x=0,y=-.6]{j} \Vertex[x=1.27,y=1.6]{k} \Vertex[x=-1.27,y=1.6]{l} \Vertex[x=0,y=-1.5]{m} \Vertex[x=2.49,y=2.05]{n} \Vertex[x=-2.49,y=2.05]{o} \Vertex[x=0,y=-4.6]{p} \Vertex[x=0,y=-5.5]{q} \Vertex[x=4.73,y=3.6]{r} \Vertex[x=5.96,y=4.05]{s} \Vertex[x=-4.73,y=3.6]{t} \Vertex[x=-5.96,y=4.05]{u} \tikzset{EdgeStyle/.style = {->}} \Edge(b)(j) \Edge(j)(a) \Edge(c)(l) \Edge(l)(a) \Edge(c)(k) \Edge(k)(b) \Edge(c)(h) \Edge(i)(a) \Edge(c)(g) \Edge(f)(b) \Edge(b)(e) \Edge(d)(a) \Edge(b)(m) \Edge(m)(a) \Edge(c)(n) \Edge(n)(b) \Edge(c)(o) \Edge(o)(a) \Edge(f)(r) \Edge(r)(g) \Edge(f)(s) \Edge(s)(g) \Edge(d)(p) \Edge(p)(e) \Edge(d)(q) \Edge(q)(e) \Edge(i)(t) \Edge(t)(h) \Edge(i)(u) \Edge(u)(h) \tikzset{EdgeStyle/.append style = {bend left}} \Edge(e)(a) \Edge(b)(d) \Edge(c)(f) \Edge(g)(b) \tikzset{EdgeStyle/.append style = {bend right}} \Edge(h)(a) \Edge(c)(i) \SetUpEdge[lw = 2.5pt, color = black, labelcolor = white, labeltext = red, labelstyle = {sloped,draw,text=blue}] \tikzset{EdgeStyle/.style = {dashed,->}} \Edge(a)(b) \Edge(b)(c) \Edge(a)(c) \Edge(e)(d) \Edge(g)(f) \Edge(h)(i) \end{tikzpicture} \end{center} \caption{The oriented planar graph $D$. The unique minimum feedback arc set of $D$ is shown in dashed lines. Note that $D$ is planar since arc $ea$ can be relocated around $abeqd$, and similarly for $gb$ and $ci$.} \label{fig:bigraph} \end{figure} % % If we can find a minimal feedback edge set which is bipartite, that is, which does not contain any odd cycles, then partitioning $D$ into 2 acyclic sets is simple: we pick vertices from one of the vertex sets of the bipartite feedback edge set to be in color class 1, and take the rest of the vertices in $D$ to be in color class 2. If either color class contains any cycles, then these cycles must avoid all feedback edges, which is a contradiction. % %However, we can construct graphs for which the minimum feedback edge set is not bipartite, as shown in figure []. A partition of the vertices of the graph in figure[] is shown: notice that for any choice of vertices covering all of the feedback edges from the minimal feedback edge set, these vertices can not all belong to one color class. %It is also natural to conjecture whether in any planar graph of relatively high digirth, there is a vertex of in-degree or out-degree at most 1. However, as shown in figure[], there is a planar digraph of arbitrarily high digirth such that the in-degree and the out-degree of every vertex is at least 2. \subsection{Improving bounds for small $g$} For small $g$, the bound we obtain in Theorem \ref{thm:main} on the maximum acyclic set of an oriented planar graph on $n$ vertices is less than $n/2$, and it is natural to ask whether we can improve upon our bound. In Propositions \ref{prop:triangle} and \ref{prop:square}, we now present two classes of planar oriented graphs, of digirth 3 and 4, respectively, for which the minimum size of a set of feedback arcs is significantly greater than $n/2$. Therefore, removing one vertex from each feedback arc yields an acyclic set of size less than $n/2$. Although some feedback arcs may overlap in certain vertices, as we demonstrate in the proof of Theorem \ref{thm:main}, applying the greedy algorithm still does not show the existence of an acyclic set of size at least $n/2$. Hence these classes of graphs suggest that the methods used in Theorem \ref{thm:main} are unlikely to prove significantly stronger bounds for digirth 3 and 4. Given a digraph $D$, let $f(D)$ denote the size of a minimum set of feedback arcs. \begin{proposition} \label{prop:triangle} There exists an infinite family of digraphs $\mathcal{D}^3$, such that for all $D\in \mathcal{D}^3$: \begin{itemize} \item $D$ is planar, with digirth 3. \item $f(D)=|V(D)|-2$. \end{itemize} \end{proposition} \begin{proof} We define $D_i\in \mathcal{D}^3$ recursively. Let $D_0$ be a directed 3-cycle, and for $i\ge 0$, construct $D_{i+1}$ as follows from a planar embedding of $D_i$. Pick some face $abc$ of $D_i$ that forms a directed 3-cycle. Construct vertices $d,e,f$ within $abc$, with arcs as shown in Figure \ref{fig:triangle}. Observe that $|V(D_{i+1})|=|V(D_i)|+3$ and $f(D_{i+1})=f(D_i)+3$. Since $|V(D_0)|=3$ and $f(D_0)=1$, it follows by induction that $f(D_i)=|V(D_i)|-2$ for every $i$. By construction, $D_i$ is planar and has digirth 3. \end{proof} \begin{figure}[ht!] \SetVertexNormal[Shape = circle, FillColor = white, LineWidth = .5pt] \SetUpEdge[lw = 1.3pt, color = black, labelcolor = white, labeltext = red, labelstyle = {sloped,draw,text=blue}] \begin{center} \begin{tikzpicture} \tikzset{VertexStyle/.style = {shape = circle,fill = pink,minimum size = 2pt,inner sep = 2.5pt}} \Vertex[x=0,y=4]{a} \Vertex[x=3.464,y=-2]{b} \Vertex[x=-3.464,y=-2]{c} \Vertex[x=0,y=-1]{d} \Vertex[x=-0.866,y=0.5]{e} \Vertex[x=0.866,y=0.5]{f} \tikzset{EdgeStyle/.style = {->}} \Edge(a)(b) \Edge(b)(c) \Edge(c)(a) \Edge(f)(a) \Edge(a)(e) \Edge(d)(b) \Edge(b)(f) \Edge(e)(c) \Edge(c)(d) \Edge(d)(e) \Edge(e)(f) \Edge(f)(d) \end{tikzpicture} \end{center} \caption{Directed octahedral pattern for generating graphs of digirth 3 with large minimum feedback arc set.} \label{fig:triangle} \end{figure} %\begin{corollary} %For $D\in \mathcal{D}^3$, removing one vertex from each of a minimum set of feedback edges yields an acyclic set with only two elements. %\end{corollary} \begin{proposition} \label{prop:square} There exists an infinite family of digraphs $\mathcal{D}^4$, such that for all $D\in \mathcal{D}^4$: \begin{itemize} \item $D$ is planar, with digirth 4. \item $f(D)=\frac{5}{8}|V(D)|-\frac{3}{2}$. \end{itemize} \end{proposition} \begin{proof} As with $\mathcal{D}^3$, we define $D_i\in \mathcal{D}^4$ recursively. Let $D_0$ be a directed 4-cycle, and for $i\ge 0$, construct $D_{i+1}$ as follows from a planar embedding of $D_i$. Pick some face $abcd$ of $D_i$ that forms a directed 4-cycle. Construct vertices $e,f,g,h,i,j,k,l$ within $abcd$, with arcs as shown in Figure \ref{fig:square}. Observe that $|V(D_{i+1})|=|V(D_i)|+8$ and $f(D_{i+1})=f(D_i)+5$. Since $|V(D_0)|=4$ and $f(D_0)=1$, it follows by induction that $f(D_i)=\frac{5}{8}|V(D_i)|-\frac{3}{2}$ for every $i$. By construction, $D_i$ is planar and has digirth 4. \end{proof} \begin{figure} \SetVertexNormal[Shape = circle, FillColor = white, LineWidth = .5pt] \SetUpEdge[lw = 1.3pt, color = black, labelcolor = white, labeltext = red, labelstyle = {sloped,draw,text=blue}] \begin{center} \begin{tikzpicture} \tikzset{VertexStyle/.style = {shape = circle,fill = pink,minimum size = 2pt,inner sep = 2.5pt}} \Vertex[x=-4,y=4]{a} \Vertex[x=4,y=4]{b} \Vertex[x=4,y=-4]{c} \Vertex[x=-4,y=-4]{d} \Vertex[x=0,y=3]{e} \Vertex[x=3,y=0]{f} \Vertex[x=0,y=-3]{g} \Vertex[x=-3,y=0]{h} \Vertex[x=-1,y=1]{i} \Vertex[x=1,y=1]{j} \Vertex[x=1,y=-1]{k} \Vertex[x=-1,y=-1]{l} \tikzset{EdgeStyle/.style = {->}} \Edge(a)(b) \Edge(b)(c) \Edge(c)(d) \Edge(d)(a) \Edge(a)(e) \Edge(e)(b) \Edge(b)(f) \Edge(f)(c) \Edge(c)(g) \Edge(g)(d) \Edge(d)(h) \Edge(h)(a) \Edge(e)(i) \Edge(i)(h) \Edge(h)(l) \Edge(l)(g) \Edge(g)(k) \Edge(k)(f) \Edge(f)(j) \Edge(j)(e) \Edge(j)(i) \Edge(k)(j) \Edge(l)(k) \Edge(i)(l) \end{tikzpicture} \end{center} \caption{Directed cuboctahedral pattern for generating graphs of digirth 4 with large minimum feedback arc set.} \label{fig:square} \end{figure} We have defined a class of digraphs $\mathcal{D}^3$ by recursive addition of an octahedral pattern, and a class $\mathcal{D}^4$ by recursive addition of a cuboctahedral pattern. It is possible to define a similar class $\mathcal{D}^5$, containing planar digraphs of digirth 5, by recursive addition of an icosidodecahedral pattern. However, the resulting relation on $f(D)$ falls short of $|V(D)|/2$:$$f(D)=\frac{11}{25}\, |V(D)|-\frac{6}{5}.$$Thus, for $D\in \mathcal{D}^5$, removing a vertex from each of a minimum set of feedback arcs yields an acyclic set of size greater than $|V(D)|/2$. We cannot say whether the methods of Theorem \ref{thm:main} may hold for general planar graphs of digirth 5. % \begin{figure} % \label{fig:pentagon} % \SetVertexNormal[Shape = circle, % FillColor = white, % LineWidth = .5pt] % \SetUpEdge[lw = 1.3pt, % color = black, % labelcolor = white, % labeltext = red, % labelstyle = {sloped,draw,text=blue}] % \begin{center} % \begin{tikzpicture} % \tikzset{VertexStyle/.style = {shape = circle,fill = pink,minimum size = 2pt,inner sep = 2.5pt}} % \Vertex[x=4 ,y=0]{a} % \Vertex[x = 1.236, y=3.804]{b} % \Vertex[x=-3.236,y=2.351]{c} % \Vertex[x=-3.236,y=-2.351]{d} % \Vertex[x=1.236,y=-3.804]{e} % \Vertex[x=2.118,y=1.532]{f} % \tikzset{EdgeStyle/.style = {->}} % \Edge(a)(b) % \Edge(b)(c) % \Edge(c)(d) % \Edge(d)(e) % \Edge(e)(a) % \Edge(d)(a) % \Edge(b)(d) % \Edge(a)(f) % \Edge(f)(b) % \end{tikzpicture} % \end{center} % \caption{A planar oriented graph with a unique minimum feedback edge set (in bold and blue) and such that any vertex cover of this set induces a directed cycle. Note that the graph is planar since edge $ea$ can be relocated around $abeqd$, and similarly for $gb$ and $ic$.} % \end{figure} \subsection*{Acknowledgements} The authors would like to thank Jacob Fox for calling our attention to this problem and Tanya Khovanova for helpful discussions and review. We would also like to thank the MIT Department of Mathematics, the Center for Excellence in Education, and the Research Science Institute for their support of this research. \begin{thebibliography}{10} \bibitem{acyclic_aharoni_2008} R.~Aharoni, E.~Berger, and O.~Kfir. \newblock Acyclic systems of representatives and acyclic colorings of digraphs. \newblock {\em Journal of Graph Theory}, pages~177--189, 2008. \bibitem{albertson_conjecture_1979} M.~O.~Albertson and D.~M.~Berman. \newblock A conjecture on planar graphs. \newblock Graph Theory and Related Topics (J.A.~Bondy and U.S.R.~Murty, eds.), page 357. Academic Press, 1979. \bibitem{circular_bokal_2004} D.~Bokal, G.~Fijav\v{z}, M.~Juvan, P.~Mark Kayll, and B.~Mohar. \newblock The circular chromatic number of a digraph. \newblock {\em Journal of Graph Theory}, 46(3):~227--240, 2004. \bibitem{borodin_acyclic_1979} O.~V.~Borodin. \newblock On acyclic colorings of planar graphs. \newblock {\em Discrete Mathematics}, 25:~211--236, 1979. \bibitem{fox_separator_2010} J.~Fox and J.~Pach. \newblock A separator theorem for string graphs and its applications. \newblock {\em Combinatorics, Probability and Computing}, 19(3):~371--390, 2010. \bibitem{harut_brooks_2011} A.~Harutyunyan. \newblock {\em Brooks-type results for coloring of digraphs}. \newblock PhD thesis, Burnaby, British Columbia, 2011. \bibitem{harut_planar_2014} A.~Harutyunyan and B.~Mohar. \newblock Planar digraphs of digirth 5 are 2-colorable, 2014. \newblock \arxiv{1401.2213} \bibitem{two_harut_2012} A.~Harutyunyan and B.~Mohar. \newblock Two results on the digraph chromatic number. \newblock {\em Discrete Mathematics}, 312(10):~1823--1826, 2012. \bibitem{generalized_jain_2005} K.~Jain, M.~T.~Hajiaghayi, and K.~Talwar. \newblock The generalized deadlock resolution problem. \newblock {\em 32nd International Colloquium on Automata, Languages and Programming}, 3580:~853--865, 2005. \bibitem{digraph_keevash_2013} P.~Keevash, Z.~Li, B.~Mohar, and B.~Reed. \newblock Digraph girth via chromatic number. \newblock {\em SIAM Journal on Discrete Mathematics}, 27(2):~693--696, 2013. \bibitem{lucchesi_minimax_1978} C.~Lucchesi and D.~H.~Younger. \newblock A minimax theorem for directed graphs. \newblock {\em Journal of London Mathematical Society}, 2:~369--374, 1978. \bibitem{vertex_neumann_1985} V.~Neumann-Lara. \newblock Vertex colorings in digraphs. Some problems. \newblock {Seminar notes, University of Waterloo}, 1985. \end{thebibliography} \end{document}