The number of dependent arcs in an acyclic orientation
Document Type
Article
Publication Title
Journal of Combinatorial Theory
Department
Mathematics
ISSN
0097-3165
Volume
71
Issue
1
DOI
10.1006/jctb.1997.1769
First Page
73
Last Page
78
Publication Date
9-1-1997
Abstract
Let G be a graph with nnodes, eedges, chromatic numberχ, and girthg. In an acyclic orientation of G, an arc is dependent if its reversal creates a cycle. It is well known that if χ<g, then G has an acyclic orientation without dependent arcs. Edelman showed that if G is connected, then every acyclic orientation has at moste−n+1 dependent arcs. We show that if G is connected and χ<g, then G has an acyclic orientation with exactly d dependent arcs for all d⩽e−n+1. We also give bounds on the minimum number of dependent arcs in graphs with χ⩾g.
Recommended Citation
Fisher, D. C.,
Fraughnaugh, K.,
West, D. B.,
&
Langley, L. L.
(1997).
The number of dependent arcs in an acyclic orientation.
Journal of Combinatorial Theory, 71(1), 73–78.
DOI: 10.1006/jctb.1997.1769
https://scholarlycommons.pacific.edu/cop-facarticles/649
