The number of dependent arcs in an acyclic orientation

DOI10.1006/jctb.1997.1769zbMath0901.05050OpenAlexW2014400460MaRDI QIDQ1386477

Kathryn Fraughnaugh, Douglas B. West, David C. Fisher, Larry J. Langley

Publication date: 10 August 1998

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/25e8dd91bae5215f220e490c4e3c4b981d49e0ea

zbMATH Keywords

chromatic numberacyclic orientationdependent arcs

Mathematics Subject Classification ID

Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)

Related Items (9)

On fully orientability of 2-degenerate graphs ⋮ Efficient enumeration of graph orientations with sources ⋮ On Minkowski sums of simplices ⋮ Non-cover generalized Mycielski, Kneser, and Schrijver graphs ⋮ On preserving full orientability of graphs ⋮ Full orientability of graphs with at most one dependent arc ⋮ Independent arcs of acyclic orientations of complete \(r\)-partite graphs ⋮ Full Orientability of Graphs ⋮ On an interpolation property of outerplanar graphs

Cites Work

• Unnamed Item
• Random graphs and covering graphs of posets
• Balanced graphs and noncovering graphs
• A short proof of the existence of highly chromatic hypergraphs without short cycles
• On the complexity of diagram testing
• Acyclic orientations of complete bipartite graphs
• Graph Theory and Probability
• On chromatic number of finite set-systems

This page was built for publication: The number of dependent arcs in an acyclic orientation