The edge chromatic difference sequence of a cubic graph Original Research Article

We study the integer sequences that might be the edge chromatic difference sequence of a cubic graph. Included in our results is a best possible lower bound for the number of edges in a maximum matching and a lower bound for the maximum number of edges in a 2-edge-colorable subgraph. We also provide examples of cubic graphs whose edge chromatic difference sequences are not monotonic. They have the property that no maximum matching extends to a maximum k-edge colorable subgraph for k = 2, 3 even though by a result of Catlin, there must exist a maximum matching that extends to a 4-edge coloring.