An adjacency lemma for critical multigraphs |
| |
Authors: | David Cariolaro |
| |
Institution: | Institute of Mathematics, Academia Sinica, Nankang, Taipei 11529, Taiwan |
| |
Abstract: | In edge colouring it is often useful to have information about the degree distribution of the neighbours of a given vertex. For example, the well-known Vizing's Adjacency Lemma provides a useful lower bound on the number of vertices of maximum degree adjacent to a given one in a critical graph. We consider an extension of this problem, where we seek information on vertices at distance two from a given vertex in a critical graph. We extend and, simultaneously, generalize to multigraphs two results proved, respectively, by Zhang Every planar graph with maximum degree seven is Class 1, Graphs Combin. 16 (2000) 467-495] and Sanders and Zhao Planar graphs of maximum degree seven are Class 1, J. Combin. Theory Ser. B 83 (2001) 201-212]. |
| |
Keywords: | 05C15 |
本文献已被 ScienceDirect 等数据库收录! |
|