Geodesic
Local chromatic number and topology
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2005_special_250_a56,
     author = {Simonyi, G\'abor and Tardos, G\'abor},
     title = {Local chromatic number and topology},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3447},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3447/}
}
TY  - JOUR
AU  - Simonyi, Gábor
AU  - Tardos, Gábor
TI  - Local chromatic number and topology
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3447/
DO  - 10.46298/dmtcs.3447
LA  - en
ID  - DMTCS_2005_special_250_a56
ER  - 
%0 Journal Article
%A Simonyi, Gábor
%A Tardos, Gábor
%T Local chromatic number and topology
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3447/
%R 10.46298/dmtcs.3447
%G en
%F DMTCS_2005_special_250_a56
Simonyi, Gábor; Tardos, Gábor. Local chromatic number and topology. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi : 10.46298/dmtcs.3447. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3447/

Cité par Sources :