A note on Hameed's conjecture on the semi-transitivity of Mycielski graphs Full article
| Journal |
Discussiones Mathematicae - Graph Theory
ISSN: 1234-3099 , E-ISSN: 2083-5892 |
||||||
|---|---|---|---|---|---|---|---|
| Output data | Year: 2025, DOI: 10.7151/dmgt.2575 | ||||||
| Tags | semi-transitive graph, semi-transitive orientation, word-representable graph, Mycielski graph, extended Mycielski graph | ||||||
| Authors |
|
||||||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0019 |
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 semitransitive extended Mycielski graphs.
Cite:
Kitaev S.
, Pyatkin A.V.
A note on Hameed's conjecture on the semi-transitivity of Mycielski graphs
Discussiones Mathematicae - Graph Theory. 2025. DOI: 10.7151/dmgt.2575 WOS OpenAlex
A note on Hameed's conjecture on the semi-transitivity of Mycielski graphs
Discussiones Mathematicae - Graph Theory. 2025. DOI: 10.7151/dmgt.2575 WOS OpenAlex
Dates:
| Submitted: | Oct 7, 2024 |
| Accepted: | Jan 4, 2025 |
| Published online: | Jan 20, 2025 |
Identifiers:
| Web of science: | WOS:001401990000001 |
| OpenAlex: | W4406677866 |
Citing:
Пока нет цитирований