Every 8-uniform 8-regular hypergraph is 2-colorable

N. Alon; Z. Bregman

doi:10.1007/BF01864169

Every 8-uniform 8-regular hypergraph is 2-colorable

N. Alon, Z. Bregman

Research output: Contribution to journal › Article › peer-review

30 Scopus citations

Abstract

As is well known, Lovász Local Lemma implies that every d-uniform d-regular hypergraph is 2-colorable, provided d ≥ 9. We present a different proof of a slightly stronger result; every d-uniform d-regular hypergraph is 2-colorable, provided d ≥ 8.

Original language	English (US)
Pages (from-to)	303-306
Number of pages	4
Journal	Graphs and Combinatorics
Volume	4
Issue number	1
DOIs	https://doi.org/10.1007/BF01864169
State	Published - Dec 1988
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/BF01864169

Cite this

@article{b1ba50b8e27347bcaed0f5f05dfd253d,

title = "Every 8-uniform 8-regular hypergraph is 2-colorable",

abstract = "As is well known, Lov{\'a}sz Local Lemma implies that every d-uniform d-regular hypergraph is 2-colorable, provided d ≥ 9. We present a different proof of a slightly stronger result; every d-uniform d-regular hypergraph is 2-colorable, provided d ≥ 8.",

author = "N. Alon and Z. Bregman",

year = "1988",

month = dec,

doi = "10.1007/BF01864169",

language = "English (US)",

volume = "4",

pages = "303--306",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "1",

}

TY - JOUR

T1 - Every 8-uniform 8-regular hypergraph is 2-colorable

AU - Alon, N.

AU - Bregman, Z.

PY - 1988/12

Y1 - 1988/12

N2 - As is well known, Lovász Local Lemma implies that every d-uniform d-regular hypergraph is 2-colorable, provided d ≥ 9. We present a different proof of a slightly stronger result; every d-uniform d-regular hypergraph is 2-colorable, provided d ≥ 8.

AB - As is well known, Lovász Local Lemma implies that every d-uniform d-regular hypergraph is 2-colorable, provided d ≥ 9. We present a different proof of a slightly stronger result; every d-uniform d-regular hypergraph is 2-colorable, provided d ≥ 8.

UR - http://www.scopus.com/inward/record.url?scp=0013306659&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0013306659&partnerID=8YFLogxK

U2 - 10.1007/BF01864169

DO - 10.1007/BF01864169

M3 - Article

AN - SCOPUS:0013306659

SN - 0911-0119

VL - 4

SP - 303

EP - 306

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 1

ER -

Every 8-uniform 8-regular hypergraph is 2-colorable

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this