On semi-transitivity of (extended) Mycielski graphs
Hameed, Humaira (2024) On semi-transitivity of (extended) Mycielski graphs. Discrete Applied Mathematics, 359. pp. 83-88. ISSN 0166-218X (https://doi.org/10.1016/j.dam.2024.07.028)
Preview |
Text.
Filename: Hameed-DAM-2024-On-semi-transitivity-of-extended-Mycielski-graphs.pdf
Final Published Version License: ![]() Download (429kB)| Preview |
Abstract
An orientation of a graph is semi-transitive if it is acyclic and shortcut-free. An undirected graph is semi-transitive if it admits a semi-transitive orientation. Semi-transitive graphs generalise several important classes of graphs and they are precisely the class of word-representable graphs studied extensively in the literature. The Mycielski graph of an undirected graph is a larger graph, constructed in a certain way, that maintains the property of being triangle-free but enlarges the chromatic number. These graphs are important as they allow to prove the existence of triangle-free graphs with arbitrarily large chromatic number. An extended Mycielski graph is a certain natural extension of the notion of a Mycielski graph that we introduce in this paper. In this paper we characterise completely semi-transitive extended Mycielski graphs and Mycielski graphs of comparability graphs. We also conjecture a complete characterisation of semi-transitive Mycielski graphs. Our studies are a far-reaching extension of the result of Kitaev and Pyatkin on non-semi-transitive orientability of the Mycielski graph µ(C5) of the cycle graph C5. Using a recent result of Kitaev and Sun, we shorten the length of the original proof of non-semi-transitive orientability of µ(C5) from 2 pages to a few lines.
-
-
Item type: Article ID code: 90209 Dates: DateEvent31 December 2024Published8 August 2024Published Online16 July 2024AcceptedSubjects: Science > Mathematics Department: Faculty of Science > Mathematics and Statistics Depositing user: Pure Administrator Date deposited: 12 Aug 2024 15:19 Last modified: 14 Aug 2024 08:31 URI: https://strathprints.strath.ac.uk/id/eprint/90209