Dependent edges in Mycielski graphs and 4‐colorings of 4‐skeletons
Karen L. Collins, Kimberly Tysdal · Journal of Graph Theory · 2004
Abstract 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 dmin(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 rm,k as the supremum of the ratio dmin(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 r4,4 ≥ 1/20. We show that r5,4 ≥ 4/71, r6,4 ≥ 7/236, and r7,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