Extending an edge‐coloring

O. Marcotte, P. D. Seymour

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

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 (Formula Presented.) 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.

Original languageEnglish (US)
Pages (from-to)565-573
Number of pages9
JournalJournal of Graph Theory
Volume14
Issue number5
DOIs
StatePublished - Nov 1990
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Extending an edge‐coloring'. Together they form a unique fingerprint.

Cite this