Stiebitz determined the chromatic number of generalised Mycielski graphs using the topological method of Lovász, which invokes the Borsuk–Ulam theorem. Van Ngoc and Tuza used elementary combinatorial arguments to prove Stiebitz's theorem for 4-chromatic generalised Mycielski graphs, and asked if there is also an elementary combinatorial proof for higher chromatic number. We answer their question by showing that Stiebitz's theorem can be deduced from a version of Fan's combinatorial lemma. Our proof uses topological terminology, but is otherwise completely discrete and could be rewritten to avoid topology altogether. However, doing so would be somewhat artificial, because we also show that Stiebitz's theorem is equivalent to the Borsuk–Ulam theorem.
@article{10_37236_8462,
author = {Tobias M\"uller and Mat\v{e}j Stehl{\'\i}k},
title = {Generalised {Mycielski} graphs and the {Borsuk-Ulam} theorem},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {4},
doi = {10.37236/8462},
zbl = {1422.05044},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8462/}
}
TY - JOUR
AU - Tobias Müller
AU - Matěj Stehlík
TI - Generalised Mycielski graphs and the Borsuk-Ulam theorem
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/8462/
DO - 10.37236/8462
ID - 10_37236_8462
ER -
%0 Journal Article
%A Tobias Müller
%A Matěj Stehlík
%T Generalised Mycielski graphs and the Borsuk-Ulam theorem
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/8462/
%R 10.37236/8462
%F 10_37236_8462
Tobias Müller; Matěj Stehlík. Generalised Mycielski graphs and the Borsuk-Ulam theorem. The electronic journal of combinatorics, Tome 26 (2019) no. 4. doi: 10.37236/8462
