SMALL GRAPHS WITH CHROMATIC NUMBER-5 - A COMPUTER-SEARCH

被引：25

作者：

JENSEN, T

ROYLE, GF

机构：

[1] Department of Combinatorics and Optimization, University of Waterloo, Waterlo, Ontario

来源：

JOURNAL OF GRAPH THEORY | 1995年 / 19卷 / 01期

关键词：

D O I：

10.1002/jgt.3190190111

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this article we give examples of a triangle-free graph on 22 vertices with chromatic number 5 and a K4-free graph on 11 vertices with chromatic number 5. We very briefly describe the computer searches demonstrating that these are the smallest possible such graphs. All 5-critical graphs on 9 vertices are exhibited. (C) 1995 John Wiley & Sons, Inc.

引用

页码：107 / 116

页数：10

共 8 条

[1] MINIMAL 5-CHROMATIC TRIANGLE-FREE GRAPHS [J].

AVIS, D .

JOURNAL OF GRAPH THEORY, 1979, 3 (04) :397-400

[2] CATALOGING THE GRAPHS ON 10 VERTICES [J].

CAMERON, RD ;

COLBOURN, CJ ;

READ, RC ;

WORMALD, NC .

JOURNAL OF GRAPH THEORY, 1985, 9 (04) :551-562

[3]

Gallai T, 1963, PUBL MATH I HUNG, V8, P373

[4]

Grinstead C. M., 1989, J COMBIN MATH COMBIN, V6, P189

[5]

Mycielski J., 1955, C MATH, V3, P161

[6]

Nenov N., 1984, CR ACAD BULGARE SCI, V37, P301

[7]

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

[8]

Toft B., 1988, 75 GRAPH COLOURING P

← 1 →