Alternation graphs
Halldorsson, Magnus and Kitaev, Sergey and Pyatkin, Artem; Kolman, Petr and Kratochvil, Jan, eds. (2011) Alternation graphs. In: Graphtheoretic concepts in computer science. Lecture Notes in Computer Science . SpringerVerlag Berlin, CZE, pp. 191202. ISBN 9783642258695 (https://doi.org/10.1007/9783642258701_18)
Full text not available in this repository.Request a copyAbstract
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 semitransitive 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 3colorable graphs. We also explore bounds on the size of the word representation of the graph. A graph G is a kalternation 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 kalternation graph. We show that the alternation number is always at most n, while there exist graphs for which it is n/2.


Item type: Book Section ID code: 34557 Dates: DateEventAugust 2011PublishedSubjects: Science > Mathematics > Electronic computers. Computer science Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 09 Nov 2011 15:08 Last modified: 03 Aug 2024 02:41 URI: https://strathprints.strath.ac.uk/id/eprint/34557