On maximum k-edge-colorable subgraphs of bipartite graphs

Abstract: If

k g e q 0

, then a

k

-edge-coloring of a graph

G

is an assignment of colors to edges of

G

from the set of

k

colors, so that adjacent edges receive different colors. A

k

-edge-colorable subgraph of

G

is maximum if it is the largest among all

k

-edge-colorable subgraphs of

G

. For a graph

G

and

k g e q 0

, let

u_{k} (G)

be the number of edges of a maximum

k

-edge-colorable subgraph of

G

. In 2010 Mkrtchyan et al. proved that if

G

is a cubic graph, then

u_{2} (G) l e q f r a c | V | + 2 u_{3} (G) 4

. This result implies that if the cubic graph

G

contains a perfect matching, in particular when it is bridgeless, then

u_{2} (G) l e q f r a c u_{1} (G) + u_{3} (G) 2

. One may wonder whether there are other interesting graph-classes, where a relation between

u_{2} (G)

and

f r a c u_{1} (G) + u_{3} (G) 2

can be proved. Related with this question, in this paper we show that

u_{k} (G) g e q f r a c u_{k - i} (G) + u_{k + i} (G) 2

for any bipartite graph

G

,

k g e q 0

and

i = 0, 1, ..., k

.

Recommendations

Cites Work

Cited In (7)

This page was built for publication: On maximum \(k\)-edge-colorable subgraphs of bipartite graphs