1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

On Semi-Transitive Orientability of Triangle-Free Graphs

Published Online: 21 Jan 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 13 Jul 2020
Accepted: 14 Nov 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

An orientation of a graph is semi-transitive if it is acyclic, and for any directed path v0v1 → → vk either there is no arc between v0 and vk, or vivj is an arc for all 0 ≤ i < jk. 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

MSC 2010

[1] P. Akrobotu, S. Kitaev and Z. Maśarova, On word-representability of polyomino triangulations, Siberian Adv. Math. 25 (2015) 1–10. doi:10.3103/S105513441501001010.3103/S1055134415010010Search in Google Scholar

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

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

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

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

[6] P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959) 34–38.10.4153/CJM-1959-003-9Search in Google Scholar

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

[8] M. Glen, Software available at personal.strath.ac.uk/sergey.kitaev/word-representable-graphs.htmlSearch in Google Scholar

[9] J. Goedgebeur, On minimal triangle-free 6-chromatic graphs, 2018. arXiv:1707.07581v310.1002/jgt.22467Search in Google Scholar

[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. doi:10.1007/978-3-642-25870-1_1810.1007/978-3-642-25870-1_18Search in Google Scholar

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

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

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

[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. doi:10.1007/978-3-319-62809-7_210.1007/978-3-319-62809-7_2Search in Google Scholar

[15] S. Kitaev and V. Lozin, Words and Graphs (Springer, 2015). doi:10.1007/978-3-319-25859-110.1007/978-3-319-25859-1Search in Google Scholar

[16] S. Kitaev and A. Saito, On semi-transitive orientability of Kneser graphs and their complements, Discrete Math. 343 (2020) 1.11909. doi:10.1016/j.disc.2020.11190910.1016/j.disc.2020.111909Search in Google Scholar

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

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

[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.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo