A note on Hameed’s conjecture on the semi-transitivity of Mycielski graphs

Tools

Kitaev, Sergey and Pyatkin, Artem (2025) A note on Hameed’s conjecture on the semi-transitivity of Mycielski graphs. Discussiones Mathematicae Graph Theory. ISSN 1234-3099 (https://doi.org/10.7151/dmgt.2575)

[thumbnail of Kitaev-Pyatkin-DMGT-2024-A-note-on-Hameeds-conjecture-on-the-semi-transitivity]
Preview
 Text. Filename: Kitaev-Pyatkin-DMGT-2024-A-note-on-Hameeds-conjecture-on-the-semi-transitivity.pdf
Final Published Version
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (232kB)| Preview

Abstract

An orientation of a graph is semi-transitive if it contains no directed cycles and has no shortcuts. An undirected graph is semi-transitive if it can be oriented in a semi-transitive manner. The class of semi-transitive graphs includes several important graph classes. The Mycielski graph of an undirected graph is a larger graph constructed in a specific manner, which maintains the property of being triangle-free but increases the chromatic number. In this note, we prove Hameed's conjecture, which states that the Mycielski graph of a graph $G$ is semi-transitive if and only if $G$ is a bipartite graph. Notably, our solution to the conjecture provides an alternative and shorter proof of the Hameed's result on a complete characterization of semi-transitive extended Mycielski graphs.

ORCID iDs

Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Pyatkin, Artem;
CORE (COnnecting REpositories)