Local chromatic number and distinguishing the strength of topological obstructions

Abstract

The local chromatic number of a graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the number of colors appearing in the most colorful closed neighborhood of a vertex minimized over all proper colorings of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We show that two specific topological obstructions that have the same implications for the chromatic number have different implications for the local chromatic number. These two obstructions can be formulated in terms of the homomorphism complex <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="hom left-parenthesis upper K 2 comma upper G right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext>Hom</mml:mtext> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>K</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mi>G</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\textrm {Hom}(K_2,G)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and its suspension, respectively. These investigations follow the line of research initiated by Matoušek and Ziegler who recognized a hierarchy of the different topological expressions that can serve as lower bounds for the chromatic number of a graph. Our results imply that the local chromatic number of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="4"> <mml:semantics> <mml:mn>4</mml:mn> <mml:annotation encoding="application/x-tex">4</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-chromatic Kneser, Schrijver, Borsuk, and generalized Mycielski graphs is <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="4"> <mml:semantics> <mml:mn>4</mml:mn> <mml:annotation encoding="application/x-tex">4</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, and more generally, that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 r"> <mml:semantics> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>r</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">2r</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-chromatic versions of these graphs have local chromatic number at least <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r plus 2"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo>+</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">r+2</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. This lower bound is tight in several cases by results of the first two authors.