TY - JOUR

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

AU - Kitaev, Sergey

AU - Pyatkin, Artem V.

N1 - Kitaev, S. A note on Hameed's conjecture on the semi-transitivity of Mycielski graphs / S. Kitaev, A. V. Pyatkin // Discussiones Mathematicae - Graph Theory. – 2025. – DOI 10.7151/dmgt.2575. – EDN RTJLCF. The authors are grateful to the referees for their valuable suggestions, which improved the presentation of the paper. The second author’s work was supported by the research project of the Sobolev Institute of Mathematics (project FWNF2022-0019).

PY - 2025/1/20

Y1 - 2025/1/20

N2 - 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.

AB - 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.

KW - semi-transitive graph

KW - semi-transitive orientation

KW - Mycielski graph

KW - extended Mycielski graph

UR - https://www.scopus.com/pages/publications/105038345742

UR - https://www.elibrary.ru/item.asp?id=81759176

UR - https://www.mendeley.com/catalogue/db9b653d-ccf5-339b-9766-6e5b4c87893d/

U2 - 10.7151/dmgt.2575

DO - 10.7151/dmgt.2575

M3 - Article

VL - 45

SP - 1157

EP - 1162

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

SN - 1234-3099

IS - 4

M1 - 5

ER -