HAJOS GRAPH-COLORING CONJECTURE - VARIATIONS AND COUNTEREXAMPLES

被引：85

作者：

CATLIN, PA

机构：

[1] Department of Mathematics, Wayne State University, Detroit

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 1979年 / 26卷 / 02期

关键词：

D O I：

10.1016/0095-8956(79)90062-5

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

For each integer n ≥ 7, we exhibit graphs of chromatic number n that contain no subdivided Kn as a subgraph. However, we show that a graph with chromatic number 4 contains as a subgraph a subdivided K4 in which each triangle of the K4 is subdivided to form an odd cycle. © 1979.

引用

页码：268 / 274

页数：7

共 10 条

[1]

Dirac Gabriel A., 1952, J LOND MATH SOC, V27, P85, DOI 10.1112/jlms/s1-27.1.85

[2]

Hadwiger Hugo, 1943, VIERTELJAHRESSCHR NA, V88, P133

[3]

Hajos G., 1961, WISS Z M LUTHER U MN, V10, P116

[4]

Harary F., 1969, GRAPH THEORY, DOI DOI 10.21236/AD0705364

[5]

JAKOBSEN IT, 1975, 1973 P C INF FIN SET, P927

[6]

Ore O., 1967, 4 COLOR PROBLEM

[7]

Toft B., 1974, Discrete Mathematics, V7, P377, DOI 10.1016/0012-365X(74)90045-4

[8]

TOFT B, 1974, JUN P S REC ADV GRAP

[9]

Tutte W.T., 1978, MATH INTELL, V1, P72

[10]

ZEIDL B, 1958, MONATSH MATH, V62, P212

← 1 →