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.

• Share and Export
  

  RefWorksRIS (EndNote Online, Zotero, Ref manager, etc)RDF+XMLEndNoteASCII CitationOpenURL ContextObject in SpanMPEG-21 DIDLRIOXX2 XMLBibTeXAtomEP3 XMLDublin CoreRDF+N-TriplesMODSHTML CitationJSONData Cite XMLRDF+N3Multiline CSVOpenURL ContextObjectReferSimple MetadataMETS
• Item metadata

  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