On semi-transitivity of (extended) Mycielski graphs

Humaira Hameed*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Downloads (Pure)

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 languageEnglish
Pages (from-to)83-88
Number of pages6
JournalDiscrete Applied Mathematics
Volume359
Early online date8 Aug 2024
DOIs
Publication statusE-pub ahead of print - 8 Aug 2024

Keywords

  • Semi-transitive graph
  • Semi-transitive orientation
  • Word-representable graph
  • Mycielski graph
  • Extended mycielski graph

Fingerprint

Dive into the research topics of 'On semi-transitivity of (extended) Mycielski graphs'. Together they form a unique fingerprint.

Cite this