2-factors in dense graphs

Noga Alon; Eldar Fischer

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

2-factors in dense graphs

Noga Alon, Eldar Fischer

Research output: Contribution to journal › Article › peer-review

34 Scopus citations

Abstract

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

Original language	English (US)
Pages (from-to)	13-23
Number of pages	11
Journal	Discrete Mathematics
Volume	152
Issue number	1-3
DOIs	https://doi.org/10.1016/0012-365X(95)00242-O
State	Published - May 20 1996
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

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

Cite this

@article{2f7a9ea63ed848bda614e18e54f29bbd,

title = "2-factors in dense graphs",

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

author = "Noga Alon and Eldar Fischer",

year = "1996",

month = may,

day = "20",

doi = "10.1016/0012-365X(95)00242-O",

language = "English (US)",

volume = "152",

pages = "13--23",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - 2-factors in dense graphs

AU - Alon, Noga

AU - Fischer, Eldar

PY - 1996/5/20

Y1 - 1996/5/20

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

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

UR - http://www.scopus.com/inward/record.url?scp=0037608154&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0037608154&partnerID=8YFLogxK

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

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

M3 - Article

AN - SCOPUS:0037608154

SN - 0012-365X

VL - 152

SP - 13

EP - 23

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

2-factors in dense graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this