On Cover Graphs and Dependent Arcs in Acyclic Orientations

Abstract

The present paper deals with two graph parameters related to cover graphs and acyclic orientations of graphs.

The parameter $c(G)$ of a graph $G$, introduced by B. Bollobás, G. Brightwell and J. Nešetril [Order 3 245–255], is defined as the minimum number of edges one needs to delete from $G$ in order to obtain a cover graph. Extending their results, we prove that, for $\delta >0$, $(1-\delta) \frac{1}{l} \frac{n^2p}{2} \leq c({\mathcal G}_{n,p}) \leq (1+\delta) \frac{1}{l} \frac{n^2p}{2}$ asymptotically almost surely as long as $C n^{-1 + \frac{1}{l}} \leq p(n) \leq c n^{-1 + \frac{1}{ l-1} }$ for some positive constants $c$ and $C$. Here, as usual, ${\mathcal G}_{n,p}$ is the random graph.

Given an acyclic orientation of a graph $G$, an arc is called dependent if its reversal creates an oriented cycle. Let $d_{\min}(G)$ be the minimum number of dependent arcs in any acyclic orientation of $G$. We determine the supremum, denoted by $r_{\chi,g}$, of $d_{\min}(G)/e(G)$ in the class of graphs $G$ with chromatic number $\chi$ and girth $g$. Namely, we show that $r_{\chi,g} = {(\scriptsize\begin{array}{@{}c@{}}{\chi}-g+2\\ 2\end{array})} / {(\scriptsize\begin{array}{@{}c@{}}{\chi}\\ 2\end{array})}$. This extends results of D. C. Fisher, K. Fraughnaugh, L. Langley and D. B. West [J. Combin. Theory Ser. B 71 73–78].

Footnotes

¹ The first author was partially supported by NSF grant DMS-0071261.

² The second author gratefully acknowledges support as a member of the Institute for Advanced Study, Princeton, NJ, where part of the work was done. The second author was also partially supported by NSF grants DMS-9970622 and DMS-0301228.