A note on semi-transitivity of Mycielski graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910561532379136 |
|---|---|
| author | Kitaev, Sergey Pyatkin, Artem |
| author_facet | Kitaev, Sergey Pyatkin, Artem |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_05066 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A note on semi-transitivity of Mycielski graphs Kitaev, Sergey Pyatkin, Artem Combinatorics 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. |
| title | A note on semi-transitivity of Mycielski graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.05066 |