Bipartite subgraphs of graphs with maximum degree three

被引：7
|
作者：
Bylka, SA [1 ]
Idzik, A [1 ]
Komar, J [1 ]
机构：
[1] Polish Acad Sci, Inst Comp Sci, PL-02137 Warsaw, Poland
来源：
GRAPHS AND COMBINATORICS | 1999年 / 15卷 / 02期
关键词：
bipartite graph; n-colourable graph; extremal graph;
D O I：
10.1007/s003730050047
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We prove that for a connected graph G with maximum degree 3 there exists a bipartite subgraph of G containing almost 3/4 of the edges of G. Furthermore, we completely characterize the set of all extremal graphs, i.e. all connected graphs G = (V, E) with maximum degree 3 for which no bipartite subgraph has more than 3 \E\ - 1/4 of the edges; \E\ denotes the cardinality of E. For 2-edge-connected graphs there are two kinds of extremal graphs which realize the lower bound 3/4 \E\.
引用
收藏
页码：129 / 136
页数：8
相关论文
共 50 条
  • [1] Bipartite Subgraphs of Graphs with Maximum Degree Three
    Stanisław Bylka
    Adam Idzik
    Jan Komar
    Graphs and Combinatorics, 1999, 15 : 129 - 136
  • [2] On maximum k-edge-colorable subgraphs of bipartite graphs
    Karapetyan, Liana
    Mkrtchyan, Vahan
    DISCRETE APPLIED MATHEMATICS, 2019, 257 : 226 - 232
  • [3] Maximum values of degree-based entropies of bipartite graphs
    Dong, Yanni
    Qiao, Shengning
    Chen, Bing
    Wan, Pengfei
    Zhang, Shenggui
    APPLIED MATHEMATICS AND COMPUTATION, 2021, 401
  • [4] Complete bipartite graphs without small rainbow subgraphs
    Ma, Zhiqiang
    Mao, Yaping
    Schiermeyer, Ingo
    Wei, Meiqin
    DISCRETE APPLIED MATHEMATICS, 2024, 346 : 248 - 262
  • [5] On the Maximum Number of Maximum Independent Sets of Bipartite Graphs
    Sun, Wanting
    Li, Shuchao
    MEDITERRANEAN JOURNAL OF MATHEMATICS, 2024, 21 (04)
  • [6] Spanning bipartite graphs with high degree sum in graphs
    Chen, Guantao
    Chiba, Shuya
    Gould, Ronald J.
    Gu, Xiaofeng
    Saito, Akira
    Tsugaki, Masao
    Yamashita, Tomoki
    DISCRETE MATHEMATICS, 2020, 343 (02)
  • [7] On the maximum ABC index of bipartite graphs without pendent vertices
    Shao, Zehui
    Wu, Pu
    Jiang, Huiqin
    Sheikholeslami, S. M.
    Wang, Shaohui
    OPEN CHEMISTRY, 2020, 18 (01): : 39 - 49
  • [8] Exploring cohesive subgraphs with vertex engagement and tie strength in bipartite graphs
    He, Yizhang
    Wang, Kai
    Zhang, Wenjie
    Lin, Xuemin
    Zhang, Ying
    INFORMATION SCIENCES, 2021, 572 : 277 - 296
  • [9] Panconnectivity in Bipartite Graphs with Large Degree sum
    Masao Tsugaki
    Tomoki Yamashita
    Takamasa Yashima
    Graphs and Combinatorics, 2023, 39
  • [10] Degree Sum Conditions for Cyclability in Bipartite Graphs
    Okamura, Haruko
    Yamashita, Tomoki
    GRAPHS AND COMBINATORICS, 2013, 29 (04) : 1077 - 1085
12345