On spanning maximum k-edge-colorable subgraphs
Vahan Mkrtchyan, Gagik N. Vardanyan · arXiv (Cornell University) · 2011
A subgraph $H$ of a graph $G$ is called spanning, if any vertex of $G$ is not isolated in $H$, while it is called maximum $k$-edge-colorable, if $H$ is $k$-edge-colorable and contains as many edges as possible. We show that any connected graph containing a matching that misses at most one vertex, has a spanning maximum 2-edge-colorable subgraph. We also show that any graph whose minimum degree is at least two and maximum degree is $r,r\geq 3$, has a spanning maximum $(r-1)$-edge-colorable subgraph. This particularly, implies that any graph whose vertices are of degree two or three, has a spanning maximum 2-edge-colorable subgraph. In the end of the paper we present a conjecture, which claims that any almost regular graph has a spanning maximum 2-edge-colorable subgraph.