𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Small graphs with chromatic number 5: A computer search

✍ Scribed by Tommy Jensen; Gordon F. Royle

Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
402 KB
Volume
19
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this article we give examples of a triangle‐free graph on 22 vertices with chromatic number 5 and a K~4~‐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. © 1995 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

A Graph with cover degeneracy less than
A Graph with cover degeneracy less than chromatic number
✍ A.V. Pyatkin 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 78 KB 👁 1 views

## Abstract This note contains an example of a 4‐chromatic graph which admits a vertex partition into three parts such that the union of every two of them induces a forest. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 243–246, 2001

On the chromatic number of a random 5-re
On the chromatic number of a random 5-regular graph
✍ J. Díaz; A. C. Kaporis; G. D. Kemkes; L. M. Kirousis; X. Pérez; N. Wormald 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 275 KB 👁 1 views

## Abstract It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5‐regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5‐regular graph is as