Alternation graphs

Magnus Halldorsson, Sergey Kitaev, Artem Pyatkin

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

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