Computer Science – Discrete Mathematics
Scientific paper
2011-07-25
Computer Science
Discrete Mathematics
12 pages, no figures
Scientific paper
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.
Mkrtchyan Vahan V.
Vardanyan Gagik N.
No associations
LandOfFree
On spanning maximum k-edge-colorable subgraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On spanning maximum k-edge-colorable subgraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On spanning maximum k-edge-colorable subgraphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-572225