Dependent edges in Mycielski graphs and 4‐colorings of 4‐skeletons

A dependent edge in an acyclic orientation of a graph is one whose reversal creates a directed cycle. In answer to a question of Erdös, Fisher et al. [5] define d min ( G ) to be the minimum number of dependent edges of a graph G , where the minimum is taken over all acyclic orientations of G , and also r m , k as the supremum of the ratio d min ( G )/ e ( G ), where e ( G ) is the number of edges in G and the supremum is taken over all graphs G with chromatic number m and girth k . They show that $r_{m,k}\le (m-2)/m$ and r 4,4 ≥ 1/20. We show that r 5,4 ≥ 4/71, r 6,4 ≥ 7/236, and r 7,4 ≥ 11/755 and that the Mycielski construction on a triangle‐free graph with at least one dependent edge yields a graph with at least three dependent edges. In addition, we give an alternative proof of the answer to Erdös's question, based on Tysdal [6] and Youngs [7]. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 285–296, 2004