✦ LIBER ✦

The chromatic numbers of random hypergraphs

✍ Scribed by Michael Krivelevich; Benny Sudakov

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 261 KB
Volume: 12
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199807)12:4<381::aid-rsa5>3.0.co;2-p

No coin nor oath required. For personal study only.

✦ Synopsis

For a pair of integers 1 F ␥r, the ␥-chromatic number of an r-uniform Ž . hypergraph H s V, E is the minimal k, for which there exists a partition of V into subsets < < T, . . . , T such that e l T F ␥ for every e g E. In this paper we determine the asymptotic 1 k i Ž . behavior of the ␥-chromatic number of the random r-uniform hypergraph H n, p for all r Ž yrq1 . possible values of ␥ and for all values of p down to p s ⌰ n .

📜 SIMILAR VOLUMES

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

On the chromatic number of disk graphs

✍ Malesi?ska, Ewa; Piskorz, Steffen; Wei�enfels, Gerhard 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB 👁 2 views

Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their

The star-chromatic number of planar grap

The star-chromatic number of planar graphs

✍ Moser, David 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 2 views

The star-chromatic number of a graph, a parameter introduced by Vince, is a natural generalization of the chromatic number of a graph. Here we construct planar graphs with star-chromatic number r, where r is any rational number between 2 and 3, partially answering a question of Vince.

On the chromatic numbers of Steiner trip

On the chromatic numbers of Steiner triple systems

✍ Lucien Haddad 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 188 KB

Geometric properties are used to determine the chromatic number of AG(4, 3) and to derive some important facts on the chromatic number of PG(n, 2). It is also shown that a 4-chromatic STS(v) exists for every admissible order v ≥ 21.

The circular chromatic number of the Myc

The circular chromatic number of the Mycielskian ofGdk

✍ Huang, Lingling; Chang, Gerard J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph G into a new graph µ(G), we now call the Mycielskian of G, which has the same clique number as G and whose chromatic number equals χ(G)+1. Chang, Huang, a

Star chromatic numbers of some planar gr

Star chromatic numbers of some planar graphs

✍ Gao, Guogang; Wang, Yiju; Zhou, Huishan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB 👁 2 views

The concept of the star chromatic number of a graph was introduced by Vince (A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551--559), which is a natural generalization of the chromatic number of a graph. This paper calculates the star chromatic numbers of three infinite families of pla