DMGT

Article in press

Authors:

S. Kitaev

Sergey Kitaev

University of Strathclyde

email: sergey.kitaev@gmail.com

A.V. Pyatkin

Artem V. Pyatkin

Sobolev Institute of MathematicsSiberian Branch ofRussian Academy of SciencesNovosibirsk, 630090RUSSIA

email: artem@math.nsc.ru

Title:

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

PDF

Source:

Discussiones Mathematicae Graph Theory

Received: 2024-10-07 , Revised: 2025-01-03 , Accepted: 2025-01-04 , Available online: 2025-01-20 , https://doi.org/10.7151/dmgt.2575

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.

Keywords:

semi-transitive graph, semi-transitive orientation, word-representable graph, Mycielski graph, extended Mycielski graph

References:

E.Z. Bidine, T. Gadi and M. Kchikech, Independence number and packing coloring of generalized Mycielski graphs, Discuss. Math. Graph Theory 41 (2021) 725–747.
https://doi.org/10.7151/dmgt.2337
H. Hameed, On semi-transitivity of $($extended$)$ Mycielski graphs, Discrete Appl. Math. 359 (2024) 83–88.
https://doi.org/10.1016/j.dam.2024.07.028
S. Kitaev and V. Lozin, Words and Graphs (Springer Cham, 2015).
https://doi.org/10.1007/978-3-319-25859-1
S.V. Kitaev and A.V. Pyatkin, Word-representable graphs: a survey, J. Appl. Ind. Math. 12 (2018) 278–296.
https://doi.org/10.1134/S1990478918020084
S. Kitaev and A. Pyatkin, On semi-transitive orientability of triangle-free graphs, Discuss. Math. Graph Theory 43 (2023) 533–547.
https://doi.org/10.7151/dmgt.2384
S. Kitaev and H. Sun, Human-verifiable proofs in the theory of word-representable graphs, in: Randomness and Combinatorics, L. Ferrari and P. Massazza (Ed(s)), RAIRO Theor. Inform. Appl. 58 (2024) 9.
https://doi.org/10.1051/ita/2024004
J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3 (1955) 161–162.
https://doi.org/10.4064/cm-3-2-161-162