A note on Hameed's conjecture on the semi-transitivity of Mycielski graphs | Sciact - Система учета научной деятельности ИМ СО РАН

A note on Hameed's conjecture on the semi-transitivity of Mycielski graphs Научная публикация

Журнал

Discussiones Mathematicae - Graph Theory
ISSN: 1234-3099 , E-ISSN: 2083-5892

Вых. Данные

Год: 2025, DOI: 10.7151/dmgt.2575

Ключевые слова

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

Авторы

Kitaev Sergey ¹ , Pyatkin Artem V. ^2,3

Организации

1	Department of Mathematics and Statistics University of Strathclyde
2	Sobolev Institute of Mathematics
3	Novosibirsk State University

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0019

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.

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

Поступила в редакцию:	7 окт. 2024 г.
Принята к публикации:	4 янв. 2025 г.
Опубликована online:	20 янв. 2025 г.

Web of science:	WOS:001401990000001
OpenAlex:	W4406677866

Пока нет цитирований