Abstract
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 | Czech Republic |
| City | Tepla |
| Period | 21/06/11 → 24/06/11 |
Keywords
- alternation graphs
- computer science
- recognition problem
Cite this
}
Alternation graphs. / Halldorsson, Magnus; Kitaev, Sergey; Pyatkin, Artem.
Graph-theoretic concepts in computer science: 37th International Workshop, WG 2011Teplá Monastery, Czech Republic, June 21-24, 2011 Revised Papers. ed. / Petr Kolman; Jan Kratochvil. Berlin, 2011. p. 191-202 (Lecture Notes in Computer Science; Vol. 6986).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book
TY - GEN
T1 - Alternation graphs
AU - Halldorsson, Magnus
AU - Kitaev, Sergey
AU - Pyatkin, Artem
PY - 2011/8
Y1 - 2011/8
N2 - 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.
AB - 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.
KW - alternation graphs
KW - computer science
KW - recognition problem
U2 - 10.1007/978-3-642-25870-1_18
DO - 10.1007/978-3-642-25870-1_18
M3 - Conference contribution book
SN - 9783642258695
T3 - Lecture Notes in Computer Science
SP - 191
EP - 202
BT - Graph-theoretic concepts in computer science
A2 - Kolman, Petr
A2 - Kratochvil, Jan
CY - Berlin
ER -