Abstract
A graph G = (V,E) is an alternation graph if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x,y) ∈ E for each x ≠ y.
In this paper we give an effective characterization of alternation graphs in terms of orientations. Namely, we show that a graph is an alternation graph if and only if it admits a semi-transitive orientation defined in the paper. This allows us to prove a number of results about alternation graphs, in particular showing that the recognition problem is in NP, and that alternation graphs include all 3-colorable graphs.
We also explore bounds on the size of the word representation of the graph. A graph G is a k-alternation graph if it is represented by a word in which each letter occurs exactly k times; the alternation number of G is the minimum k for which G is a k-alternation graph. We show that the alternation number is always at most n, while there exist graphs for which it is n/2.
In this paper we give an effective characterization of alternation graphs in terms of orientations. Namely, we show that a graph is an alternation graph if and only if it admits a semi-transitive orientation defined in the paper. This allows us to prove a number of results about alternation graphs, in particular showing that the recognition problem is in NP, and that alternation graphs include all 3-colorable graphs.
We also explore bounds on the size of the word representation of the graph. A graph G is a k-alternation graph if it is represented by a word in which each letter occurs exactly k times; the alternation number of G is the minimum k for which G is a k-alternation graph. We show that the alternation number is always at most n, while there exist graphs for which it is n/2.
Original language | English |
---|---|
Title of host publication | Graph-theoretic concepts in computer science |
Subtitle of host publication | 37th International Workshop, WG 2011Teplá Monastery, Czech Republic, June 21-24, 2011 Revised Papers |
Editors | Petr Kolman, Jan Kratochvil |
Place of Publication | Berlin |
Pages | 191-202 |
Number of pages | 12 |
DOIs | |
Publication status | Published - Aug 2011 |
Event | 37th International workshop on graph-theoretic concepts in computer science, 2011 - Tepla, Czech Republic Duration: 21 Jun 2011 → 24 Jun 2011 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 6986 |
ISSN (Print) | 0302-9743 |
Conference
Conference | 37th International workshop on graph-theoretic concepts in computer science, 2011 |
---|---|
Country/Territory | Czech Republic |
City | Tepla |
Period | 21/06/11 → 24/06/11 |
Keywords
- alternation graphs
- computer science
- recognition problem