Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number

DOI10.1016/0012-365X(87)90101-4zbMath0624.05049OpenAlexW2054534871MaRDI QIDQ1092065

Jeanette P. Schmidt

Publication date: 1987

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(87)90101-4

zbMATH Keywords

algorithmsrandom hypergraphssparse hypergraphscoloring problemsstrong chromatic numberstrong coloring algorithmsweak colorings

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15)

Related Items

On the strong chromatic number of random hypergraphs, On the \(s\)-colorful number of a random hypergraph, General independence sets in random strongly sparse hypergraphs, On the concentration of values of \(j\)-chromatic numbers of random hypergraphs, Bounds on threshold probabilities for coloring properties of random hypergraphs, On the concentration of the independence numbers of random hypergraphs, Estimating the strong \(r\)-colorability threshold in random hypergraphs, Two-Colorings of a Random Hypergraph, On the strong chromatic number of a random 3-uniform hypergraph, On the weak chromatic number of random hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Component structure in the evolution of random hypergraphs
• Couplages et transversaux généralises d'un hypergraphe infini
• Sur la cardinalite maximum des couplages d'hypergraphes aléatoires uniformes
• A threshold for perfect matchings in random d-pure hypergraphs
• Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
• Random hypergraph coloring algorithms and the weak chromatic number
• Asymptotical Estimations for the Number of Cliques of Uniform Hypergraphs
• Cliques in random graphs