Abstract | ||
---|---|---|
Fix a palette K of Delta + 1 colors, a graph with maximum degree., and a subset M of the edge set with minimum distance between edges at least 9. If the edges of M are arbitrarily precoloured from K, then there is guaranteed to be a proper edge-coloring using only colors from K that extends the precolouring on M to the entire graph. This result is a first general precolouring extension form of Vizing's theorem, and it proves a conjecture of Albertson and Moore under a slightly stronger distance requirement. We also show that the condition on the distance can be lowered to 5 when the graph contains no cycle of length 5. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1002/jgt.22451 | JOURNAL OF GRAPH THEORY |
Keywords | DocType | Volume |
edge-coloring,precolouring extension,Vizing's theorem | Journal | 92 |
Issue | ISSN | Citations |
3 | 0364-9024 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
António Girão | 1 | 1 | 3.07 |
Ross J. Kang | 2 | 86 | 18.12 |