𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Chromatic numbers of products of graphs: The directed and undirected versions of the Poljak-Rödl function

✍ Scribed by Claude Tardif; David Wehlau

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
61 KB
Volume
51
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let f(n) = min{χ(G × H) : G and H are n‐chromatic digraphs} and g(n) = min{χ(G × H) : G and H are n‐chromatic graphs}. We prove that f is bounded if and only if g is bounded. © 2005 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Some upper bounds for the product of the
Some upper bounds for the product of the domination number and the chromatic number of a graph
✍ Jerzy Topp; Lutz Volkmann 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 199 KB

Topp, J. and L. Volkmann, Some upper bounds for the product of the domination number and the chromatic number of a graph, Discrete Mathematics 118 (1993) 2899292. Some new upper bounds for yx are proved, where y is the domination number and x is the chromatic number of a graph. All graphs consider

Density of the circular chromatic number
Density of the circular chromatic numbers of series-parallel graphs
✍ Zhishi Pan; Xuding Zhu 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB 👁 1 views

## Abstract Suppose __G__ is a series‐parallel graph. It was proved in 3 that either ~χ__c__~(__G__) = 3 or ~χ__c__~(__G__) ≤ 8/3. So none of the rationals in the interval (8/3, 3) is the circular chromatic number of a series‐parallel graph. This paper proves that for every rational __r__ ∈ [2, 8/3