Alternation graphs
Halldorsson, Magnus and Kitaev, Sergey and Pyatkin, Artem; Kolman, Petr and Kratochvil, Jan, eds. (2011) Alternation graphs. In: Graph-theoretic concepts in computer science. Lecture Notes in Computer Science . Springer-Verlag Berlin, CZE, pp. 191-202. ISBN 9783642258695 (https://doi.org/10.1007/978-3-642-25870-1_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 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.
ORCID iDs
Halldorsson, Magnus, Kitaev, Sergey ORCID: https://orcid.org/0000-0003-3324-1647 and Pyatkin, Artem; Kolman, Petr and Kratochvil, Jan-
-
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: 11 Nov 2024 14:45 URI: https://strathprints.strath.ac.uk/id/eprint/34557