Alternation graphs

Magnus Halldorsson, Sergey Kitaev, Artem Pyatkin

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

9 Citations (Scopus)

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.
LanguageEnglish
Title of host publicationGraph-theoretic concepts in computer science
Subtitle of host publication37th International Workshop, WG 2011Teplá Monastery, Czech Republic, June 21-24, 2011 Revised Papers
EditorsPetr Kolman, Jan Kratochvil
Place of PublicationBerlin
Pages191-202
Number of pages12
DOIs
Publication statusPublished - Aug 2011
Event37th International workshop on graph-theoretic concepts in computer science, 2011 - Tepla, Czech Republic
Duration: 21 Jun 201124 Jun 2011

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume6986
ISSN (Print)0302-9743

Conference

Conference37th International workshop on graph-theoretic concepts in computer science, 2011
CountryCzech Republic
CityTepla
Period21/06/1124/06/11

Keywords

  • alternation graphs
  • computer science
  • recognition problem

Cite this

Halldorsson, M., Kitaev, S., & Pyatkin, A. (2011). Alternation graphs. In P. Kolman, & J. Kratochvil (Eds.), Graph-theoretic concepts in computer science: 37th International Workshop, WG 2011Teplá Monastery, Czech Republic, June 21-24, 2011 Revised Papers (pp. 191-202). (Lecture Notes in Computer Science; Vol. 6986). Berlin. https://doi.org/10.1007/978-3-642-25870-1_18
Halldorsson, Magnus ; Kitaev, Sergey ; Pyatkin, Artem. / Alternation graphs. Graph-theoretic concepts in computer science: 37th International Workshop, WG 2011Teplá Monastery, Czech Republic, June 21-24, 2011 Revised Papers. editor / Petr Kolman ; Jan Kratochvil. Berlin, 2011. pp. 191-202 (Lecture Notes in Computer Science).
@inproceedings{9d3b812fa43c4980bf5f9b4bd1a6b513,
title = "Alternation graphs",
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.",
keywords = "alternation graphs, computer science, recognition problem",
author = "Magnus Halldorsson and Sergey Kitaev and Artem Pyatkin",
year = "2011",
month = "8",
doi = "10.1007/978-3-642-25870-1_18",
language = "English",
isbn = "9783642258695",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "191--202",
editor = "Kolman, {Petr } and Kratochvil, {Jan }",
booktitle = "Graph-theoretic concepts in computer science",

}

Halldorsson, M, Kitaev, S & Pyatkin, A 2011, Alternation graphs. in P Kolman & J Kratochvil (eds), Graph-theoretic concepts in computer science: 37th International Workshop, WG 2011Teplá Monastery, Czech Republic, June 21-24, 2011 Revised Papers. Lecture Notes in Computer Science, vol. 6986, Berlin, pp. 191-202, 37th International workshop on graph-theoretic concepts in computer science, 2011, Tepla, Czech Republic, 21/06/11. https://doi.org/10.1007/978-3-642-25870-1_18

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 proceedingConference 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 -

Halldorsson M, Kitaev S, Pyatkin A. Alternation graphs. In Kolman P, Kratochvil J, editors, Graph-theoretic concepts in computer science: 37th International Workshop, WG 2011Teplá Monastery, Czech Republic, June 21-24, 2011 Revised Papers. Berlin. 2011. p. 191-202. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-25870-1_18