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

共 15 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2] LARGEST BIPARTITE SUBGRAPHS IN TRIANGLE-FREE GRAPHS WITH MAXIMUM DEGREE 3 [J].

BONDY, JA ;

LOCKE, SC .

JOURNAL OF GRAPH THEORY, 1986, 10 (04) :477-504

[3] On colouring the nodes of a network [J].

Brooks, RL .

PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1941, 37 :194-197

[4]

BYLKA S, 1991, ICS PAS REPORTS, V701

[5]

Erdos, 1967, MATH LAPOK, V18, P283

[6] ON SOME EXTREMAL PROBLEMS IN GRAPH THEORY [J].

ERDOS, P .

ISRAEL JOURNAL OF MATHEMATICS, 1965, 3 (02) :113-&

[7]

Erdos P., 1979, Graph Theory and Related Topics, Proc. Conf. (Waterloo, ON, P153

[8] EXTREMAL BIPARTITE SUBGRAPHS OF CUBIC TRIANGLE-FREE GRAPHS [J].

HOPKINS, G ;

STATON, W .

JOURNAL OF GRAPH THEORY, 1982, 6 (02) :115-121

[9] A NOTE ON BIPARTITE SUBGRAPHS OF TRIANGLE-FREE REGULAR GRAPHS [J].

LOCKE, SC .

JOURNAL OF GRAPH THEORY, 1990, 14 (02) :181-185

[10] MAXIMUM K-COLORABLE SUBGRAPHS [J].

LOCKE, SC .

JOURNAL OF GRAPH THEORY, 1982, 6 (02) :123-132

← 1 2 →