On maximum k-edge-colorable subgraphs of bipartite graphs
On maximum k-edge-colorable subgraphs of bipartite graphs
复制标题
关于二部图的最大k边可着色子图
DOI：
10.1016/j.dam.2018.10.013
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
V. Mkrtchyan
中科院分区：
文献类型：
--
作者：
Liana Karapetyan;V. Mkrtchyan
如果k≥0，则图G的k边着色是从k个颜色集合中给G的边分配颜色，使相邻的边得到不同的颜色。对于图G且k≥0，设ν k (G)为G的最大k边可着色子图的边数。2010年Mkrtchyan等证明了如果G是一个三次图，则ν 2 (G)≤| V|+ 2 ν 3 (G) 4。这个结果表明，如果三次图G包含一个完美匹配，特别是当它是无桥的，那么ν 2 (G)≤ν 1 (G)+ ν 3 (G) 2。有人可能想知道是否有其他有趣的图类，其中可以证明ν 2 (G)和ν 1 (G)+ ν 3 (G) 2之间的关系。与此问题相关，本文证明了对于任意二部图G， k≥0且i= 0,1，…，k, ν k (G)≥ν k−i (G)+ ν k+ i (G) 2。
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)≥ ν k− i (G)+ ν k+ i (G) 2 for any bipartite graph G, k≥ 0 and i= 0, 1,…, k.