Article in volume
Authors:
Title:
On semi-transitive orientability of triangle-free graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(2) (2023) 533-547
Received: 2020-07-13 , Revised: 2020-11-14 , Accepted: 2020-11-14 , Available online: 2020-12-18 , https://doi.org/10.7151/dmgt.2384
Abstract:
An orientation of a graph is semi-transitive if it is acyclic, and for any
directed path $v_0\rightarrow v_1\rightarrow \cdots\rightarrow v_k$ either there
is no arc between $v_0$ and $v_k$, or $v_i\rightarrow v_j$ is an arc for all
$0\leq i<j\leq 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ötzsch graph, Mycielski graph, Chvátal graph, Toft's graph, circulant graph, Toeplitz graph
References:
- 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 - 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 - F. Boesch and R. Tindell, Circulants and their connectivity, J. Graph Theory 8 (1984) 487–499.
https://doi.org/10.1002/jgt.3190080406 - 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 - 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 - P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959) 34–38.
- S.H. Ghorban, Toeplitz graph decomposition, Trans. Comb. 1(4) (2012) 35–41.
- M. Glen, Software (available at).
personal.strath.ac.uk/sergey.kitaev/word-representable-graphs.html - J. Goedgebeur, On minimal triangle-free $6$-chromatic graphs (2018).
arXiv: 1707.07581v3 - 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 - 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 - 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 - T.R. Jensen and B. Toft, Graph Coloring Problems (New York, John Wiley & Sons, 1995).
https://doi.org/10.1002/9781118032497 - 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 - S. Kitaev and V. Lozin, Words and Graphs (Springer, 2015).
https://doi.org/10.1007/978-3-319-25859-1 - 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 - W. Pegden, Critical graphs without triangles: An optimum density construction, Combinatorica 33 (2013) 495–512.
https://doi.org/10.1007/s00493-013-2440-1 - B. Toft, On the maximal number of edges of critical k-chromatic graphs, Studia Sci. Math. Hungar. 5 (1970) 461–470.
- 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.
Close