✦ LIBER ✦

Critical hypergraphs for the weak chromatic number

✍ Scribed by C Benzaken

Publisher: Elsevier Science
Year: 1980
Tongue: English
Weight: 732 KB
Volume: 29
Category: Article
ISSN: 0095-8956
DOI: 10.1016/0095-8956(80)90090-8

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Random hypergraph coloring algorithms an

Random hypergraph coloring algorithms and the weak chromatic number

✍ Jeanette Schmidt-Pruzan; Eli Shamir; Eli Upfal 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 610 KB

We present a hypergraph coloring algorithm and analyze its performance in spaces of random hypergraphs. In these spaces the number of colors used by our algorithm is almost surely within a small constant factor (less than 2) of the weak chromatic number of the hypergraph. This also establishes new u

Post's closed systems and the weak chrom

Post's closed systems and the weak chromatic number of hypergraphs

✍ C. Benzaken 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 689 KB

In the Post lattice of the families of closed systems (r.e. sets CT ooolean functions closed with respect to composition) the particular systems of mionotonic functions are closely related to the classitication of hypergraphs by their weak chromatic numbers. It is shown also that ffor k r 3, the k-c

The chromatic numbers of random hypergra

The chromatic numbers of random hypergraphs

✍ Michael Krivelevich; Benny Sudakov 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB 👁 1 views

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 n

The independence number of an edge-chrom

The independence number of an edge-chromatic critical graph

✍ Douglas R. Woodall 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 77 KB 👁 1 views

A graph G with maximum degree and edge chromatic number (G)> is edge--critical if (G -e) = for every edge e of G. It is proved here that the vertex independence number of an edge--critical graph of order n is less than 3 5 n. For large , this improves on the best bound previously known, which was ro

A new upper bound for the independence n

A new upper bound for the independence number of edge chromatic critical graphs

✍ Rong Luo; Yue Zhao 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB 👁 2 views

In 1968, Vizing conjectured that if G is a -critical graph with n vertices, then (G) ≤ n / 2, where (G) is the independence number of G. In this paper, we apply Vizing and Vizing-like adjacency lemmas to this problem and prove that (G)<(((5 -6)n) / (8 -6))<5n / 8 if ≥ 6. ᭧ 2010 Wiley

The enumeration problem for color critic

The enumeration problem for color critical linear hypergraphs

✍ H.L Abbott; A Liu; B Toft 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 682 KB