2021/02/04 by Danila Cherkashin, Cherkashin, Danila, Alexey Gordeev +1
Computer Science · Mathematics · Engineering · #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2102.02746
We give an upper bound on the list chromatic number of a 2-colorable hypergraph which generalizes the bound of Schauz on k-partite k-uniform hypergraphs. It makes sense for sparse hypergraphs: in particular we show that a k-uniform k-regular hypergraph has the list chromatic number 2 for k ≥ 4. Also we obtain both lower and upper bound on the list chromatic number of a complete s-uniform 2-colorable hypergraph in the vein of Erd\H os--Rubin--Taylor theorem.