Coloring parameters for graphs on surfaces |
| |
| Institution: | 1. Department of Mathematics, London School of Economics and Political Science, London, United Kingdom;2. Centre d’Analyse et de Mathématiques Sociales (CNRS, UMR 8557), Paris, France;3. Computer Science Institute of Charles University (IUUK), Prague, Czech Republic;4. Logic and Semantics, Technical University Berlin, Germany;5. Institute of Informatics, Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland;1. Department of Mathematics, London School of Economics and Political Science, London WC2A 2AE, UK;2. School of Mathematical and Statistical Sciences, Arizona State University, Tempe, AZ 85287, USA |
| |
| Abstract: | We overview several coloring parameters with the property that they are bounded on graphs whose (Euler) genus is bounded. Besides the usual chromatic number, we treat the acyclic, the star and the degenerate chromatic number, we discuss some of their relatives, and we determine their dependence on the genus. Extensions to more general classes of graphs (minor-closed families and classes of bounded expansion) are also discussed. The probabilistic method, which is used in proving both upper and lower bounds, gives the dependence of the treated coloring parameters in terms of the maximum degree, a result which is of independent interest. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
