Extending an edge‐coloring
- 1 November 1990
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 14 (5) , 565-573
- https://doi.org/10.1002/jgt.3190140508
Abstract
When can a k‐edge‐coloring of a subgraph K of a graph G be extended to a k‐edge‐coloring of G? One necessary condition is that for all X ⊆ E(G) ‐ E(K), where μi(X) is the maximum cardinality of a subset of X whose union with the set of edges of K colored i is a matching. This condition is not sufficient in general, but is sufficient for graphs of very simple structure. We try to locate the border where sufficiency ends.Keywords
This publication has 3 references indexed in Scilit:
- The NP-Completeness of Edge-ColoringSIAM Journal on Computing, 1981
- On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and TutteProceedings of the London Mathematical Society, 1979
- Maximum matching and a polyhedron with 0,1-verticesJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965