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.
Original language | English |
---|---|
Pages (from-to) | 83-88 |
Number of pages | 6 |
Journal | Discrete Applied Mathematics |
Volume | 359 |
Early online date | 8 Aug 2024 |
DOIs | |
Publication status | E-pub ahead of print - 8 Aug 2024 |
Keywords
- Semi-transitive graph
- Semi-transitive orientation
- Word-representable graph
- Mycielski graph
- Extended mycielski graph