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

✍ Scribed by Karen L. Collins; Kimberly Tysdal

• Publisher: John Wiley and Sons
• Year: 2004
• Tongue: English
• Weight: 174 KB
• Volume: 46
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20007

✦ Synopsis

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 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