✦ LIBER ✦

A Graph with cover degeneracy less than chromatic number

✍ Scribed by A.V. Pyatkin

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 78 KB
Volume: 37
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.1019

No coin nor oath required. For personal study only.

✦ Synopsis

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

📜 SIMILAR VOLUMES

The chromatic covering number of a graph

✍ Reza Naserasr; Claude Tardif 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB 👁 2 views

Following [1] , we investigate the problem of covering a graph G with induced subgraphs G 1 ; . . . ; G k of possibly smaller chromatic number, but such that for every vertex u of G, the sum of reciprocals of the chromatic numbers of the G i 's containing u is at least 1. The existence of such ''ch

Small graphs with chromatic number 5: A

Small graphs with chromatic number 5: A computer search

✍ Tommy Jensen; Gordon F. Royle 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 402 KB

## 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‐critica