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

*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

}

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

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 -