On semi-transitivity of (extended) Mycielski graphs

Tools

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)

[thumbnail of Hameed-DAM-2024-On-semi-transitivity-of-extended-Mycielski-graphs]
Preview
 Text. Filename: Hameed-DAM-2024-On-semi-transitivity-of-extended-Mycielski-graphs.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
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:
    Date
    Event
    31 December 2024
    Published
    8 August 2024
    Published Online
    16 July 2024
    Accepted
    Subjects:Science > Mathematics
    Department:Faculty of Science > Mathematics and Statistics
    Depositing user: Pure Administrator
    Date deposited:12 Aug 2024 15:19
    Last modified:02 Dec 2024 01:30
    URI:https://strathprints.strath.ac.uk/id/eprint/90209
CORE (COnnecting REpositories)