Alternation graphs

Magnus Halldorsson; Sergey Kitaev; Artem Pyatkin

doi:10.1007/978-3-642-25870-1_18

Alternation graphs

Magnus Halldorsson, Sergey Kitaev, Artem Pyatkin

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

12 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.

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	https://doi.org/10.1007/978-3-642-25870-1_18
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

Access to Document

10.1007/978-3-642-25870-1_18

Cite this

@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 = aug,

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",

note = "37th International workshop on graph-theoretic concepts in computer science, 2011 ; Conference date: 21-06-2011 Through 24-06-2011",

}

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

T2 - 37th International workshop on graph-theoretic concepts in computer science, 2011

Y2 - 21 June 2011 through 24 June 2011

ER -