Alternation Graphs
Alternation Graphs
复制标题
交替图
DOI：
10.1007/978-3-642-25870-1_18
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
A. Pyatkin
中科院分区：
文献类型：
--
作者：
M. Halldórsson;S. Kitaev;A. Pyatkin
图G =（V，E）是一个交错图，如果在字母V上存在一个字W，使得字母x和y在W中交错，当且仅当对于每个x和y，（x，y）∈ E.本文给出了交错图的一个有效的方向刻画.也就是说，我们证明了一个图是交错图当且仅当它允许本文定义的半传递定向。这使我们能够证明一些结果的交替图，特别是表明，识别问题是在NP，交替图包括所有3-colorable graphs.We还探讨了边界上的大小的字表示的图。一个图G是ak-交替图，如果它用一个词表示，其中每个字母恰好出现k次; G的交替数k是G是ak-交替图的最小值。我们表明，交替数总是在momentum，而存在的图，它不是/2。
A graphG= (V,E) is analternation graphif there exists a wordWover the alphabetVsuch that lettersxandyalternate inWif and only if (x,y) ∈Efor eachx≠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 asemi-transitive orientationdefined 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 graphGis ak-alternationgraph if it is represented by a word in which each letter occurs exactlyktimes; the alternation number ofGis the minimumkfor whichGis ak-alternation graph. We show that the alternation number is always at mostn, while there exist graphs for which it isn/2.