The Number of Dependent Arcs in an Acyclic Orientation

LetGbe a graph withnnodes,eedges, chromatic numberχ, and girthg. In an acyclic orientation ofG, an arc isdependentif its reversal creates a cycle. It is well known that ifχ

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series B 1997-09, Vol.71 (1), p.73-78
Main Authors: Fisher, David C., Fraughnaugh, Kathryn, Langley, Larry, West, Douglas B.
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:LetGbe a graph withnnodes,eedges, chromatic numberχ, and girthg. In an acyclic orientation ofG, an arc isdependentif its reversal creates a cycle. It is well known that ifχ
ISSN:0095-8956
1096-0902
DOI:10.1006/jctb.1997.1769