n-Tuple Coloring of Planar Graphs with Large Odd Girth |
| |
| Authors: | William Klostermeyer Cun Quan Zhang |
| |
| Institution: | (1) Department of Computer and Information Sciences, University of North Florida, Jacksonville, FL 32224, USA. e-mail: klostermeyer@hotmail.com, US;(2) Department of Mathematics, P. O. Box 6310, West Virginia University, Morgantown, WV 26506, USA. e-mail: cqzhang@math.wvu.edu, US |
| |
| Abstract: | The main result of the papzer is that any planar graph with odd girth at least 10k−7 has a homomorphism to the Kneser graph G
k
2
k
+1, i.e. each vertex can be colored with k colors from the set {1,2,…,2k+1} so that adjacent vertices have no colors in common. Thus, for example, if the odd girth of a planar graph is at least
13, then the graph has a homomorphism to G
2
5, also known as the Petersen graph. Other similar results for planar graphs are also obtained with better bounds and additional
restrictions.
Received: June 14, 1999 Final version received: July 5, 2000 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
