2-factors in dense graphs

被引：29

作者：

Alon, N ^{[1
]}

Fischer, E ^{[1
]}

机构：

[1] TEL AVIV UNIV,RAYMOND & BEVERLY SACKLER FAC EXACT SCI,DEPT MATH,IL-69978 TEL AVIV,ISRAEL

来源：

DISCRETE MATHEMATICS | 1996年 / 152卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(95)00242-O

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A conjecture of Sauer and Spencer states that any graph G on n vertices with minimum degree at least 2/3n contains any graph H on n vertices with maximum degree 2 or less. This conjecture is proven here for all sufficiently large n.

引用

页码：13 / 23

页数：11

共 12 条

[1] ALMOST H-FACTORS IN DENSE GRAPHS [J].

ALON, N ;

YUSTER, R .

GRAPHS AND COMBINATORICS, 1992, 8 (02) :95-102

[2] THE STRONG CHROMATIC NUMBER OF A GRAPH [J].

ALON, N .

RANDOM STRUCTURES & ALGORITHMS, 1992, 3 (01) :1-7

[3]

ALON N, IN PRESS J COMBIN B

[4]

BOLLOBAS B, 1978, P C INT CNRS

[5]

Bollobas B., 1978, EXTREMAL GRAPH THEOR

[6]

Bondy J.A., 1971, J COMBINATORIAL THEO, V11, P80

[7] TAIL OF THE HYPERGEOMETRIC DISTRIBUTION [J].

CHVATAL, V .

DISCRETE MATHEMATICS, 1979, 25 (03) :285-287

[8]

Corradi K., 1963, Acta Math. Acad. Sci. Hungar, V14, P423

[9] ON CIRCUITS IN GRAPHS [J].

ELZAHAR, MH .

DISCRETE MATHEMATICS, 1984, 50 (2-3) :227-230

[10] EDGE DISJOINT PLACEMENT OF GRAPHS [J].

SAUER, N ;

SPENCER, J .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1978, 25 (03) :295-302

← 1 2 →