Every graph of sufficiently large average degree contains a C4-Free subgraph of large average degree

被引：21

作者：

Kühn, D

Osthus, D

机构：

[1] Free Univ Berlin, Inst Math, D-14195 Berlin, Germany

[2] Humboldt Univ, Inst Informat, D-10099 Berlin, Germany

来源：

COMBINATORICA | 2004年 / 24卷 / 01期

关键词：

D O I：

10.1007/s00493-004-0010-2

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that for every k there exists d=d(k) such that every graph of average degree at least d contains a subgraph of average degree at least k and girth at least six. This settles a special case of a conjecture of Thomassen.

引用

页码：155 / 162

页数：8

共 6 条

[1]

[Anonymous], 1969, PROOF TECHNIQUES GRA

[2]

Diestel R., 1997, Graph Theory

[3] REGULAR SUBGRAPHS OF DENSE GRAPHS [J].

PYBER, L .

COMBINATORICA, 1985, 5 (04) :347-349

[4] DENSE GRAPHS WITHOUT 3-REGULAR SUBGRAPHS [J].

PYBER, L ;

RODL, V ;

SZEMEREDI, E .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 63 (01) :41-54

[5] CHROMATIC NUMBER OF SUBGRAPHS OF A GIVEN GRAPH [J].

RODL, V .

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1977, 64 (02) :370-371

[6] GIRTH IN GRAPHS [J].

THOMASSEN, C .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1983, 35 (02) :129-141

← 1 →