2018/07/17 by Liana Karapetyan, Karapetyan, Liana, Vahan Mkrtchyan +1
Computer Science · Mathematics · Neuroscience · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Nuclear Receptors and Signaling
paper · pdf · doi:10.48550/arxiv.1807.06556
openalex publication_date 2018/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
If k≥ 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≥ 0, let ν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 ν2(G)≤ (|V|+2ν3(G))/(4). This result implies that if the cubic graph G contains a perfect matching, in particular when it is bridgeless, then ν2(G)≤ (ν1(G)+ν3(G))/(2). One may wonder whether there are other interesting graph-classes, where a relation between ν2(G) and (ν1(G)+ν3(G))/(2) can be proved. Related with this question, in this paper we show that νk(G) ≥ \fracνk-i(G) + νk+i(G)2 for any bipartite graph G, k≥ 0 and i=0,1,...,k.