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 条
  • [31] Finding bipartite subgraphs efficiently
    Mubayi, Dhruv
    Turan, Gyoergy
    INFORMATION PROCESSING LETTERS, 2010, 110 (05) : 174 - 177
  • [32] Characterizing degree-sum maximal nonhamiltonian bipartite graphs
    Ferrara, Michael
    Jacobson, Michael
    Powell, Jeffrey
    DISCRETE MATHEMATICS, 2012, 312 (02) : 459 - 461
  • [33] Accelerating maximum biplex search over large bipartite graphs
    Pan, Dong
    Zhou, Xu
    Luo, Wensheng
    Yang, Zhibang
    Liu, Qing
    Gao, Yunjun
    Li, Kenli
    VLDB JOURNAL, 2025, 34 (01):
  • [34] Convex bipartite graphs and bipartite circle graphs
    Kizu, T
    Haruta, Y
    Araki, T
    Kashiwabara, T
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 1998, E81A (05) : 789 - 795
  • [35] On vertex-disjoint complete bipartite subgraphs in a bipartite graph
    Wang, H
    GRAPHS AND COMBINATORICS, 1999, 15 (03) : 353 - 364
  • [36] Partitioning the vertex set of a bipartite graph into complete bipartite subgraphs
    Duginov, Oleg
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2014, 16 (03): : 203 - 214
  • [37] Edge cover by connected bipartite subgraphs
    Leo Liberti
    Laurent Alfandari
    Marie-Christine Plateau
    Annals of Operations Research, 2011, 188 : 307 - 329
  • [38] On Vertex-Disjoint Complete Bipartite Subgraphs in a Bipartite Graph
    Hong Wang
    Graphs and Combinatorics, 1999, 15 : 353 - 364
  • [39] Finding the Maximum k-Balanced Biclique on Weighted Bipartite Graphs
    Zhao, Yiwei
    Chen, Zi
    Chen, Chen
    Wang, Xiaoyang
    Lin, Xuemin
    Zhang, Wenjie
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2023, 35 (08) : 7994 - 8007
  • [40] Efficient Exact Algorithms for Maximum Balanced Biclique Search in Bipartite Graphs
    Chen, Lu
    Liu, Chengfei
    Zhou, Rui
    Xu, Jiajie
    Li, Jianxin
    SIGMOD '21: PROCEEDINGS OF THE 2021 INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 2021, : 248 - 260
12345