On semi-transitive orientability of Kneser graphs and their complements
On semi-transitive orientability of Kneser graphs and their complements
复制标题
克内泽图及其补图的半传递可定向性
DOI：
10.1016/j.disc.2020.111909
复制
发表时间：
2020
影响因子：
0.8
通讯作者：
S. Kitaev and A. Saito
中科院分区：
文献类型：
--
作者：
Okumura Keisuke;Machida Manao;Defago Xavier;Tamura Yasumasa;S. Kitaev and A. Saito
一个图的方向是半传递的，如果它是非圈的，并且对于任何有向路v 0→v 1→⋯→v k，在v 0和v k之间不存在边，或者v i→v j是所有0≤i<；j≤k的边。如果一个无向图具有半传递方向，则它是半传递的。半传递图包括三色图、可比图、圈图等几类重要的图，它们正是文献中广泛研究的一类词可表示图。本文研究了著名的K(n，k)图的半传递方向性，K(n，k)是指其顶点对应于一个n元集合的k元子集的图，且其中两个顶点相邻当且仅当两个对应的集合不相交。证明了K(n，k)对于任意偶数k≥2和n≥3 k以及对任意奇数k≥3和n≥3 k+3都不是半传递的.另一方面，对于m∈{2 k，2 k+1}，K(n，k)是半传递的.此外，如果K(p，q)不是半传递的，则K(n，k)对于任何k≥q和n≥k q p都不是半传递的.此外，我们通过计算证明了K(8，3)不是半传递的，这使得对于任何k≥3和n≥8⋅k3，K(n，k)都不是半传递的.我们提出的K(8，3)的某个子图S和K(8，3)本身是无三角形非半传递图的第一个显式例子.它的存在性是由Halldórsson，Kitaev和Pyatkin在ő等人(2011年)通过Erd-De，Kitaev和Pyatkin定理建立的。最后，K(n，k)的补图K(n，k)‘不是半传递的当且仅当n>；2k。
An orientation of a graph is semi-transitive if it is acyclic, and for any directed path v 0→ v 1→⋯→ v k either there is no edge between v 0 and v k, or v i→ v j is an edge for all 0≤ i< j≤ k. An undirected graph is semi-transitive if it admits a semi-transitive orientation. Semi-transitive graphs include several important classes of graphs such as 3-colourable graphs, comparability graphs, and circle graphs, and they are precisely the class of word-representable graphs studied extensively in the literature. In this paper, we study semi-transitive orientability of the celebrated Kneser graph K (n, k), which is the graph whose vertices correspond to the k-element subsets of a set of n elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. We show that K (n, k) is not semi-transitive for any even integers k≥ 2 and n≥ 3 k and for any odd integers k≥ 3 and n≥ 3 k+ 3. On the other hand, for m∈{2 k, 2 k+ 1}, K (n, k) is semi-transitive. Also, if K (p, q) is not semi-transitive, then K (n, k) is not semi-transitive for any k≥ q and n≥ k q p. Moreover, we show computationally that K (8, 3) is not semi-transitive, which results in K (n, k) being not semi-transitive for any k≥ 3 and n≥ 8⋅ k 3. A certain subgraph S of K (8, 3) presented by us and K (8, 3) itself are the first explicit examples of triangle-free non-semi-transitive graphs, whose existence was established via Erdős’ theorem by Halldórsson, Kitaev and Pyatkin in Halldórsson et al.(2011). Finally, the complement graph K (n, k)¯ of K (n, k) is not semi-transitive if and only if n> 2 k.
登录
查看更多内容
折线图的文字表示能力
DOI：
10.4236/ojdm.2011.12012
发表时间：
2011
期刊：
影响因子：
--
作者：
S. Kitaev;P. Salimov;Christopher Severs;Henning Úlfarsson
通讯作者：
Henning Úlfarsson
基于有向无环图的珀金斯半群文字问题
影响因子：
0.4
作者：
S. Kitaev;S. Seif
通讯作者：
S. Seif
多骨牌三角剖分的词可表示性
DOI：
10.3103/s1055134415010010
发表时间：
2014
期刊：
影响因子：
--
作者：
P. Akrobotu;S. Kitaev;Zuzana Mas'arov'a
通讯作者：
Zuzana Mas'arov'a
文字表示图的新结果
影响因子：
1.1
作者：
Andrew Collins;S. Kitaev;V. Lozin
通讯作者：
V. Lozin
DOI：
10.1007/978-3-642-25870-1_18
发表时间：
2011
期刊：
International Workshop on Graph-Theoretic Concepts in Computer Science
影响因子：
--
作者：
M. Halldórsson;S. Kitaev;A. Pyatkin
通讯作者：
A. Pyatkin