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 →