Geodesic
On semi-transitive orientability of triangle-free graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 533-547 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 arc between v_0 and v_k, or v_i→ v_j is an arc for all 0≤ i lt;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 Erdős' 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.
Keywords: semi-transitive orientation, triangle-free graph, Gr\"otzsch graph, Mycielski graph, Chv\'atal graph, Toft's graph, circulant graph, Toeplitz graph 
@article{DMGT_2023_43_2_a14,
     author = {Kitaev, Sergey and Pyatkin, Artem V.},
     title = {On semi-transitive orientability of triangle-free graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {533--547},
     year = {2023},
     volume = {43},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a14/}
}
TY  - JOUR
AU  - Kitaev, Sergey
AU  - Pyatkin, Artem V.
TI  - On semi-transitive orientability of triangle-free graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 533
EP  - 547
VL  - 43
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a14/
LA  - en
ID  - DMGT_2023_43_2_a14
ER  - 
%0 Journal Article
%A Kitaev, Sergey
%A Pyatkin, Artem V.
%T On semi-transitive orientability of triangle-free graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 533-547
%V 43
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a14/
%G en
%F DMGT_2023_43_2_a14
Kitaev, Sergey; Pyatkin, Artem V. On semi-transitive orientability of triangle-free graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 533-547. http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a14/

[1] P. Akrobotu, S. Kitaev and Z. Maśarova, On word-representability of polyomino triangulations, Siberian Adv. Math. 25 (2015) 1–10. https://doi.org/10.3103/S1055134415010010

[2] J.-C. Bermond, F. Comellas and D.F. Hsu, Distributed loop computer networks: A survey, J. Parallel Distributed Comput. 24 (1995) 2–10. https://doi.org/10.1006/jpdc.1995.1002

[3] F. Boesch and R. Tindell, Circulants and their connectivity, J. Graph Theory 8 (1984) 487–499. https://doi.org/10.1002/jgt.3190080406

[4] G.-S. Cheon, J. Kim, M. Kim and S. Kitaev, Word-representability of Toeplitz graphs, Discrete Appl. Math. 270 (2019) 96–105. https://doi.org/10.1016/j.dam.2019.07.013

[5] V. Chvátal, The smallest triangle-free 4-chromatic 4-regular graph, J. Combin. Theory 9 (1970) 93–94. https://doi.org/10.1016/S0021-9800(70)80057-6

[6] P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959) 34–38.

[7] S.H. Ghorban, Toeplitz graph decomposition, Trans. Comb. 1(4) (2012) 35–41.

[8] M. Glen, \textrm{ Software} (available at). personal.strath.ac.uk/sergey.kitaev/word-representable-graphs.html

[9] J. Goedgebeur, On minimal triangle-free 6-chromatic graphs (2018). arXiv: 1707.07581v3

[10] M.M. Halldórsson, S. Kitaev and A. Pyatkin, Alternation graphs, in: Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 6986 (2011) 191–202. https://doi.org/10.1007/978-3-642-25870-1_18

[11] M.M. Halldórsson, S. Kitaev and A. Pyatkin, Semi-transitive orientations and word-representable graphs, Discrete Appl. Math. 201 (2016) 164–171. https://doi.org/10.1016/j.dam.2015.07.033

[12] C. Heuberger, On planarity and colorability of circulant graphs, Discrete Math. 268 (2003) 153–169. https://doi.org/10.1016/S0012-365X(02)00685-4

[13] T.R. Jensen and B. Toft, Graph Coloring Problems (New York, John Wiley & Sons, 1995). https://doi.org/10.1002/9781118032497

[14] S. Kitaev, A comprehensive introduction to the theory of word-representable graphs, in: Developments in Language Theory, Lecture Notes in Comput. Sci. 10396 (2017) 36–67. https://doi.org/10.1007/978-3-319-62809-7_2

[15] S. Kitaev and V. Lozin, Words and Graphs (Springer, 2015). https://doi.org/10.1007/978-3-319-25859-1

[16] S. Kitaev and A. Saito, On semi-transitive orientability of Kneser graphs and their complements, Discrete Math. 343 (2020) 111909. https://doi.org/10.1016/j.disc.2020.111909

[17] W. Pegden, Critical graphs without triangles: An optimum density construction, Combinatorica 33 (2013) 495–512. https://doi.org/10.1007/s00493-013-2440-1

[18] B. Toft, On the maximal number of edges of critical k-chromatic graphs, Studia Sci. Math. Hungar. 5 (1970) 461–470.

[19] L.M. Vitaver, Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix, Dokl. Akad. Nauk SSSR 147 (1962) 758–759, in Russian.