Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
On Semi-Transitive Orientability of Triangle-Free Graphs. / Kitaev, Sergey; Pyatkin, Artem.
в: Discussiones Mathematicae - Graph Theory, 2021.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - On Semi-Transitive Orientability of Triangle-Free Graphs
AU - Kitaev, Sergey
AU - Pyatkin, Artem
N1 - Publisher Copyright: © 2020 Sergey Kitaev et al., published by Sciendo. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.
PY - 2021
Y1 - 2021
N2 - An orientation of a graph is semi-transitive if it is acyclic, and for any directed path v0 → v1 → → vk either there is no arc between v0 and vk, or vi → vj is an arc for all 0 ≤ i < j ≤ k. An undirected graph is semi-transitive if it admits a semi-transitive orientation. Semi-transitive graphs generalize several important classes of graphs and they are precisely the class of word-representable graphs studied extensively in the literature. Determining if a triangle-free graph is semi-transitive is an NP-hard problem. The existence of non-semi-transitive triangle-free graphs was established via Erdos' theorem by Halldórsson and the authors in 2011. However, no explicit examples of such graphs were known until recent work of the first author and Saito who have shown computationally that a certain subgraph on 16 vertices of the triangle-free Kneser graph K(8, 3) is not semi-transitive, and have raised the question on the existence of smaller triangle-free non-semi-transitive graphs. In this paper we prove that the smallest triangle-free 4-chromatic graph on 11 vertices (the Grötzsch graph) and the smallest triangle-free 4-chromatic 4-regular graph on 12 vertices (the Chvátal graph) are not semi-transitive. Hence, the Grötzsch graph is the smallest triangle-free non-semi-transitive graph. We also prove the existence of semi-transitive graphs of girth 4 with chromatic number 4 including a small one (the circulant graph C(13; 1, 5) on 13 vertices) and dense ones (Toft's graphs). Finally, we show that each 4-regular circulant graph (possibly containing triangles) is semi-transitive.
AB - An orientation of a graph is semi-transitive if it is acyclic, and for any directed path v0 → v1 → → vk either there is no arc between v0 and vk, or vi → vj is an arc for all 0 ≤ i < j ≤ k. An undirected graph is semi-transitive if it admits a semi-transitive orientation. Semi-transitive graphs generalize several important classes of graphs and they are precisely the class of word-representable graphs studied extensively in the literature. Determining if a triangle-free graph is semi-transitive is an NP-hard problem. The existence of non-semi-transitive triangle-free graphs was established via Erdos' theorem by Halldórsson and the authors in 2011. However, no explicit examples of such graphs were known until recent work of the first author and Saito who have shown computationally that a certain subgraph on 16 vertices of the triangle-free Kneser graph K(8, 3) is not semi-transitive, and have raised the question on the existence of smaller triangle-free non-semi-transitive graphs. In this paper we prove that the smallest triangle-free 4-chromatic graph on 11 vertices (the Grötzsch graph) and the smallest triangle-free 4-chromatic 4-regular graph on 12 vertices (the Chvátal graph) are not semi-transitive. Hence, the Grötzsch graph is the smallest triangle-free non-semi-transitive graph. We also prove the existence of semi-transitive graphs of girth 4 with chromatic number 4 including a small one (the circulant graph C(13; 1, 5) on 13 vertices) and dense ones (Toft's graphs). Finally, we show that each 4-regular circulant graph (possibly containing triangles) is semi-transitive.
KW - Chvátal graph
KW - circulant graph
KW - Grötzsch graph
KW - Mycielski graph
KW - semi-transitive orientation
KW - Toeplitz graph
KW - Toft's graph
KW - triangle-free graph
UR - http://www.scopus.com/inward/record.url?scp=85100710347&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/3347768a-1118-3477-a305-74d31a06d1b9/
U2 - 10.7151/dmgt.2384
DO - 10.7151/dmgt.2384
M3 - Article
AN - SCOPUS:85100710347
JO - Discussiones Mathematicae - Graph Theory
JF - Discussiones Mathematicae - Graph Theory
SN - 1234-3099
ER -
ID: 27878063