Local chromatic number and distinguishing the strength of topological obstructions

DOI10.1090/S0002-9947-08-04643-6zbMATH Open1170.05027arXivmath/0502452OpenAlexW1973273044MaRDI QIDQ3605849FDOQ3605849

Authors: Gábor Simonyi, Gábor Tardos, Siniša T. Vrećica 

Publication date: 25 February 2009

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Abstract: The local chromatic number of a graph G is the number of colors appearing in the most colorful closed neighborhood of a vertex minimized over all proper colorings of G. 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 Hom(K_2,G) and its suspension, respectively. These investigations follow the line of research initiated by Matousek 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 4-chromatic Kneser, Schrijver, Borsuk, and generalized Mycielski graphs is 4, and more generally, that 2r-chromatic versions of these graphs have local chromatic number at least r+2. This lower bound is tight in several cases by results in an earlier paper of the first two authors.

Full work available at URL: https://arxiv.org/abs/math/0502452

Recommendations

• scientific article; zbMATH DE number 5763218
• Local chromatic number, Ky Fan's theorem, and circular colorings
• Topological obstructions to graph colorings
• Local coloring of Kneser graphs
• Topological lower bounds for the chromatic number: a hierarchy

zbMATH Keywords

Borsuk-Ulam theorembox complexlocal chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Relations of low-dimensional topology with graph theory (57M15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph Theory and Probability
• Title not available (Why is that?)
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
• Kneser's conjecture, chromatic number, and homotopy
• A short proof of Kneser's conjecture
• Title not available (Why is that?)
• The Chromatic Number of Kneser Hypergraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Coloring graphs with locally few colors
• Complexes of graph homomorphisms
• Colorful subgraphs in Kneser-like graphs
• Local chromatic number and Sperner capacity
• Title not available (Why is that?)
• Local chromatic number, Ky Fan's theorem, and circular colorings
• Chromatic numbers of quadrangulations on closed surfaces
• 4-chromatic projective graphs
• A generalization of Tucker's combinatorial lemma with topological applications
• Equivariant Cohomology and Lower Bounds for Chromatic Numbers
• Equivalent Formulations of the Borsuk-Ulam Theorem
• Topological lower bounds for the chromatic number: a hierarchy
• Fractional chromatic numbers of cones over graphs
• Antipodal Coincidence for Maps of Spheres into Complexes
• Evenly distributed subsets of \(S^ n\) and a combinatorial application
• On graphs with strongly independent color-classes
• Neighborhood complexes of stable Kneser graphs
• Bier spheres and barycentric subdivision
• Homotopy types of box complexes
• Coloring locally bipartite graphs on surfaces.
• From graphs to ortholattices and equivariant maps
• WI-posets, graph complexes and \(\mathbb{Z}_2\)-equivalences
• Local chromatic number of quadrangulations of surfaces
• Title not available (Why is that?)
• Coincidence and The Colouring of Maps
• Title not available (Why is that?)

Cited In (15)

• Local chromatic number of quadrangulations of surfaces
• Title not available (Why is that?)
• Dynamic coloring of graphs having no \(K_5\) minor
• Local chromatic number, Ky Fan's theorem, and circular colorings
• Homomorphism complexes, reconfiguration, and homotopy for directed graphs
• A generalization of the Erdős-Ko-Rado theorem
• On inverse powers of graphs and topological implications of Hedetniemi's conjecture
• Title not available (Why is that?)
• Local orthogonality dimension
• Generalised Mycielski graphs, signature systems, and bounds on chromatic numbers
• Obstructions to locally injective oriented improper colourings
• On topological relaxations of chromatic conjectures
• On directed local chromatic number, shift graphs, and Borsuk-like graphs
• Colorings of complements of line graphs
• Altermatic number of categorical product of graphs

This page was built for publication: Local chromatic number and distinguishing the strength of topological obstructions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3605849)