Title

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.

Link to Full Text

Share

COinS