Name
Abstract | ||
|---|---|---|
Suppose that D is an acyclic orientation of a graph G. An arc of D is called dependent if its reversal creates a directed cycle. Let d(min)(G) (d(max) (G)) denote the minimum (maximum) of the number of dependent arcs over all acyclic orientations of G. We call G fully orientable if G has an acyclic orientation with exactly d dependent arcs for every d satisfying d(min)(G) <= d <= d(max)(G). A graph G is called chordal if every cycle in G of length at least four has a chord. We show that all chordal graphs are fully orientable. |
Year | Venue | Keywords |
|---|---|---|
2015 | ARS COMBINATORIA | acyclic orientation,full orientability,simplicial vertex,chordal graph |
DocType | Volume | ISSN |
Journal | 122 | 0381-7032 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hsin-Hao Lai | 1 | 13 | 3.19 |
| Ko-wei Lih | 2 | 529 | 58.80 |