✦ LIBER ✦

The chromatic covering number of a graph

✍ Scribed by Reza Naserasr; Claude Tardif

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 72 KB
Volume: 51
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20127

No coin nor oath required. For personal study only.

✦ Synopsis

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 ''chromatic coverings'' provides some bounds on the chromatic number of G.

📜 SIMILAR VOLUMES

Chromatic numbers of hypergraphs and cov

Chromatic numbers of hypergraphs and coverings of graphs

✍ Zevi Miller; Heinrich Müller 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 284 KB

Burr recently proved [3] that for positive integers m , , m 2 , . . , , m, and any graph G we have x(G) 5 &, if and only if G can be expressed as the edge disjoint union of subgraphs F, satisfying x(F,) 5 m,. This theorem is generalized to hypergraphs. By suitable interpretations the generalization

The star chromatic number of a graph

✍ H. L. Abbott; B. Zhou 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 469 KB 👁 1 views

## Abstract We study a generalization of the notion of the chromatic number of a graph in which the colors assigned to adjacent vertices are required to be, in a certain sense, far apart. © 1993 John Wiley & Sons, Inc.

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

Rank and chromatic number of a graph

✍ Kotlov, Andrei? 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 2 views

It was proved (A. Kotlov and L. Lovász, The rank and size of graphs, J. Graph Theory 23 (1996), 185-189) that the number of vertices in a twin-free graph is O(( √ 2) r ) where r is the rank of the adjacency matrix. This bound was shown to be tight. We show that the chromatic number of a graph is o(∆

The chromatic number of oriented graphs

✍ Sopena, Eric 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 2 views

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with

Bounds for the harmonious chromatic numb

Bounds for the harmonious chromatic number of a graph

✍ I. Krasikov; Y. Roditty 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 231 KB 👁 1 views

## Abstract The upper bound for the harmonious chromatic number of a graph given by Zhikang Lu and by C. McDiarmid and Luo Xinhua, independently (__Journal of Graph Theory__, 1991, pp. 345–347 and 629–636) and the lower bound given by D. G. Beane, N. L. Biggs, and B. J. Wilson (__Journal of Graph T