Premium
Extending an edge‐coloring
Author(s) -
Marcotte O.,
Seymour P. D.
Publication year - 1990
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190140508
Subject(s) - combinatorics , mathematics , edge coloring , cardinality (data modeling) , graph , simple graph , matching (statistics) , enhanced data rates for gsm evolution , simple (philosophy) , complete coloring , list coloring , discrete mathematics , line graph , graph power , computer science , telecommunications , philosophy , statistics , epistemology , data mining
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\documentclass{article}\pagestyle{empty}\begin{document}$$ |{\rm X}|\, \le \,\sum\limits_{1 \le {\rm i} \le {\rm k}} {\mu _i ({\rm X})} $$\end{document}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.