Dense uniform hypergraphs have high list chromatic number

Noga Alon; Alexandr Kostochka

doi:10.1016/j.disc.2011.05.013

Dense uniform hypergraphs have high list chromatic number

Noga Alon, Alexandr Kostochka

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

5 Scopus citations

Abstract

The first author showed that the list chromatic number of every graph with average degree d is at least (0.5-o(1))log2d. We prove that for r<3, every r-uniform hypergraph in which at least half of the (r-1)-vertex subsets are contained in at least d edges has list chromatic number at least lnd100r3. When r is fixed, this is sharp up to a constant factor.

Original language	English (US)
Pages (from-to)	2119-2125
Number of pages	7
Journal	Discrete Mathematics
Volume	312
Issue number	14
DOIs	https://doi.org/10.1016/j.disc.2011.05.013
State	Published - Jul 28 2012
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Keywords

Co-degree
Hypergraph
List coloring

Access to Document

10.1016/j.disc.2011.05.013

Cite this

@article{01427d34ed4a4afb81ab01193bdcb959,

title = "Dense uniform hypergraphs have high list chromatic number",

abstract = "The first author showed that the list chromatic number of every graph with average degree d is at least (0.5-o(1))log2d. We prove that for r<3, every r-uniform hypergraph in which at least half of the (r-1)-vertex subsets are contained in at least d edges has list chromatic number at least lnd100r3. When r is fixed, this is sharp up to a constant factor.",

keywords = "Co-degree, Hypergraph, List coloring",

author = "Noga Alon and Alexandr Kostochka",

note = "Funding Information: The authors thank the referees for helpful comments and suggestions. The research of the first author was supported in part by an ERC advanced grant, by a USA-Israeli BSF grant, by the Oswald Veblen Fund and by the Bell Companies Fellowship. The research of the second author was supported in part as by NSF grant DMS-0965587 and by grant 09-01-00244 of the Russian Foundation for Basic Research.",

year = "2012",

month = jul,

day = "28",

doi = "10.1016/j.disc.2011.05.013",

language = "English (US)",

volume = "312",

pages = "2119--2125",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "14",

}

TY - JOUR

T1 - Dense uniform hypergraphs have high list chromatic number

AU - Alon, Noga

AU - Kostochka, Alexandr

N1 - Funding Information: The authors thank the referees for helpful comments and suggestions. The research of the first author was supported in part by an ERC advanced grant, by a USA-Israeli BSF grant, by the Oswald Veblen Fund and by the Bell Companies Fellowship. The research of the second author was supported in part as by NSF grant DMS-0965587 and by grant 09-01-00244 of the Russian Foundation for Basic Research.

PY - 2012/7/28

Y1 - 2012/7/28

N2 - The first author showed that the list chromatic number of every graph with average degree d is at least (0.5-o(1))log2d. We prove that for r<3, every r-uniform hypergraph in which at least half of the (r-1)-vertex subsets are contained in at least d edges has list chromatic number at least lnd100r3. When r is fixed, this is sharp up to a constant factor.

AB - The first author showed that the list chromatic number of every graph with average degree d is at least (0.5-o(1))log2d. We prove that for r<3, every r-uniform hypergraph in which at least half of the (r-1)-vertex subsets are contained in at least d edges has list chromatic number at least lnd100r3. When r is fixed, this is sharp up to a constant factor.

KW - Co-degree

KW - Hypergraph

KW - List coloring

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

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

U2 - 10.1016/j.disc.2011.05.013

DO - 10.1016/j.disc.2011.05.013

M3 - Article

AN - SCOPUS:84860881778

SN - 0012-365X

VL - 312

SP - 2119

EP - 2125

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 14

ER -

Dense uniform hypergraphs have high list chromatic number

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this