Planar graphs without cycles of specific lengths

被引：64

作者：

Fijavz, G ^{[1
]}

Juvan, M ^{[1
]}

Mohar, B ^{[1
]}

Skrekovski, R ^{[1
]}

机构：

[1] Univ Ljubljana, Dept Math, Ljubljana 1111, Slovenia

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2002年 / 23卷 / 04期

关键词：

D O I：

10.1006/eujc.2002.0570

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It is easy to see that planar graphs without 3-cycles are 3-degenerate. Recently, it was proved that planar graphs without 5-cycles are also 3-degenerate. In this paper it is shown, more surprisingly, that the same holds for planar graphs without 6-cycles. (C) 2002 Elsevier Science Ltd. All rights reserved.

引用

页码：377 / 388

页数：12

共 13 条

[1]

Alon N., 1993, LONDON MATH SOC LECT, V187, P1

[2] The complexity of planar graph choosability [J].