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

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/Territory | Czech Republic |

City | Tepla |

Period | 21/06/11 → 24/06/11 |

## Keywords

- alternation graphs
- computer science
- recognition problem