Gábor Simonyi ; Gábor Tardos - Local chromatic number and topology

dmtcs:3447 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3447
Local chromatic number and topologyArticle

Authors: Gábor Simonyi 1; Gábor Tardos 1

  • 1 Alfréd Rényi Institute of Mathematics

The local chromatic number of a graph, introduced by Erdős et al., is the minimum number of colors that must appear in the closed neighborhood of some vertex in any proper coloring of the graph. This talk would like to survey some of our recent results on this parameter. We give a lower bound for the local chromatic number in terms of the lower bound of the chromatic number provided by the topological method introduced by Lovász. We show that this bound is tight in many cases. In particular, we determine the local chromatic number of certain odd chromatic Schrijver graphs and generalized Mycielski graphs. We further elaborate on the case of $4$-chromatic graphs and, in particular, on surface quadrangulations.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: graph coloring,topological method,Schrijver graphs,Mycielski graphs,surface quadrangulation,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

2 Documents citing this article

Consultation statistics

This page has been seen 171 times.
This article's PDF has been downloaded 354 times.