Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650255 | Discrete Mathematics | 2008 | 5 Pages |
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
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
David Cariolaro,