Premium
Multipass greedy coloring of simple uniform hypergraphs
Author(s) -
Kozik Jakub
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20613
Subject(s) - hypergraph , combinatorics , van der waerden's theorem , mathematics , simple (philosophy) , vertex (graph theory) , upper and lower bounds , simple graph , graph , discrete mathematics , mathematical analysis , philosophy , epistemology
Letm * ( n ) be the minimum number of edges in an n ‐uniform simple hypergraph that is not two colorable. We prove thatm * ( n ) = Ω ( 4 n / ln 2 ( n ) ) . Our result generalizes to r ‐coloring of b ‐simple uniform hypergraphs. For fixed r and b we prove that a maximum vertex degree in b ‐simple n ‐uniform hypergraph that is not r ‐colorable must be Ω ( r n / ln ( n ) ) . By trimming arguments it implies that every such graph has Ω ( ( r n / ln ( n ) ) b + 1 / b ) edges. For any fixed r ⩾ 2 our techniques yield also a lower bound Ω ( r n / ln ( n ) ) for van der Waerden numbers W ( n, r ). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 125–146, 2016