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 条
  • [41] An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs
    Das, Shibsankar
    SCIENTIFIC ANNALS OF COMPUTER SCIENCE, 2020, 30 (01) : 25 - 37
  • [42] Bipartite Subgraphs and Quasi-Randomness
    Jozef Skokan
    Lubos Thoma
    Graphs and Combinatorics, 2004, 20 : 255 - 262
  • [43] Packing bipartite graphs with covers of complete bipartite graphs
    Chalopin, Jeremie
    Paulusma, Daniel
    DISCRETE APPLIED MATHEMATICS, 2014, 168 : 40 - 50
  • [44] Extremal Graphs for Even Linear Forests in Bipartite Graphs
    Yuan, Long-Tu
    Zhang, Xiao-Dong
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2024, 44 (01) : 5 - 16
  • [45] Hamiltonian cycles in bipartite toroidal graphs with a partite set of degree four vertices
    Fujisawa, Jun
    Nakamoto, Atsuhiro
    Ozeki, Kenta
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2013, 103 (01) : 46 - 60
  • [46] Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs
    Coelho, H.
    Faria, L.
    Gravier, S.
    Klein, S.
    DISCRETE APPLIED MATHEMATICS, 2016, 198 : 109 - 117
  • [47] Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs
    Doron-Arad, Ilan
    Shachnai, Hadas
    DISCRETE APPLIED MATHEMATICS, 2025, 361 : 453 - 464
  • [48] Distance spectral radius of unicyclic graphs with fixed maximum degree
    Huang, Hezan
    Zhou, Bo
    JOURNAL OF ALGEBRA AND ITS APPLICATIONS, 2020, 19 (04)
  • [49] Minimally Non-Preperfect Graphs of Small Maximum Degree
    Zsolt Tuza
    Annegret Wagler
    Graphs and Combinatorics, 2001, 17 : 759 - 773
  • [50] Extremal bipartite graphs with high girth
    Balbuena, C.
    Garcia-Vazquez, P.
    Marcote, X.
    Valenzuela, J. C.
    ARS COMBINATORIA, 2007, 83 : 3 - 14
12345