Improved bounds and algorithms for hypergraph 2-coloring
From MaRDI portal
Publication:4943351
DOI<4::AID-RSA2>3.0.CO;2-2 10.1002/(SICI)1098-2418(200001)16:1<4::AID-RSA2>3.0.CO;2-2zbMath0942.05024OpenAlexW2039241885WikidataQ56444802 ScholiaQ56444802MaRDI QIDQ4943351
Aravind Srinivasan, Jaikumar Radhakrishnan
Publication date: 16 August 2000
Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(200001)16:1<4::aid-rsa2>3.0.co;2-2
Hypergraphs (05C65) Parallel algorithms in computer science (68W10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items (70)
The Strong Fractional Choice Number and the Strong Fractional Paint Number of Graphs ⋮ A note on random greedy coloring of uniform hypergraphs ⋮ Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs ⋮ The Minimum Number of Edges in Uniform Hypergraphs with Property O ⋮ On general two-colorings of uniform hypergraphs ⋮ Conflict-Free Colourings of Uniform Hypergraphs With Few Edges ⋮ Unsplittable coverings in the plane ⋮ Extremal problems for colorings of simple hypergraphs and applications ⋮ Equitable colorings of non-uniform simple hypergraphs ⋮ Multipass greedy coloring of simple uniform hypergraphs ⋮ DP-colorings of uniform hypergraphs and splittings of Boolean hypercube into faces ⋮ Improper Choosability and Property B ⋮ Chain method for panchromatic colorings of hypergraphs ⋮ A note on two-colorability of nonuniform hypergraphs ⋮ Lower bounds in the combinatorial problem of Erdős and Lovász ⋮ On some generalizations of the property B problem of an \(n\)-uniform hypergraph ⋮ The intersection spectrum of 3‐chromatic intersecting hypergraphs ⋮ Colorings of \(b\)-simple hypergraphs ⋮ DP-colorings of hypergraphs ⋮ The list-chromatic number of complete multipartite hypergraphs and multiple covers by independent sets ⋮ Improved algorithms for colorings of simple hypergraphs and applications ⋮ Some new bounds on partition critical hypergraphs ⋮ List Coloring with a Bounded Palette ⋮ 2-colorings of hypergraphs with large girth ⋮ Extremal problems in hypergraph colourings ⋮ Lower bounds for the number of edges in hypergraphs of certain classes ⋮ Combinatorial extremum problems for 2-colorings of hypergraphs ⋮ On colorings of 3-homogeneous hypergraphs in 3 colors ⋮ Equitable two-colorings of uniform hypergraphs ⋮ Colorings of hypergraphs with large number of colors ⋮ Improvement of the lower bound in the Kostochka problem of panchromatic coloring of a hypergraph ⋮ Majority problems of large query size ⋮ Colorings of hypergraphs with large number of colors ⋮ On two-colorings of hypergraphs ⋮ On \(r\)-chromatic hypergraphs ⋮ On the construction of non-2-colorable uniform hypergraphs ⋮ Random hypergraphs and property B ⋮ Blocking sets of the classical unital ⋮ Colourings of Uniform Hypergraphs with Large Girth and Applications ⋮ 2-colorings of uniform hypergraphs ⋮ On a generalization of Rubin's theorem ⋮ On the chromatic number of set systems ⋮ The Cayley isomorphism property for Cayley maps ⋮ Coloring cross-intersecting families ⋮ Inclusion/exclusion meets measure and conquer ⋮ On balanced colorings of hypergraphs ⋮ Unnamed Item ⋮ Improved Bounds for Uniform Hypergraphs without Property B ⋮ Greedy colorings of uniform hypergraphs ⋮ Coloring H-free hypergraphs ⋮ Constructions of sparse uniform hypergraphs with high chromatic number ⋮ On proper colourings of hypergraphs using prescribed colours ⋮ Chip games and paintability ⋮ Colorings of partial Steiner systems and their applications ⋮ Improvement of the lower bound in the Erdös-Hajnal combinatorial problem ⋮ On equitable colorings of hypergraphs ⋮ Coloring non-uniform hypergraphs without short cycles ⋮ On the chromatic number of simple triangle-free triple systems ⋮ Coloring hypergraphs with bounded cardinalities of edge intersections ⋮ List colorings of multipartite hypergraphs ⋮ On the chromatic number of finite systems of subsets ⋮ Measurable versions of the Lovász local lemma and measurable graph colorings ⋮ Random coloring method in the combinatorial problem of Erdős and Lovász ⋮ On the Problem of Erdős and Hajnal in the Case of List Colorings ⋮ New lower bound for the minimal number of edges of simple uniform hypergraph without the property \(B_k\) ⋮ On 2-coloring certain \(k\)-uniform hypergraphs ⋮ On non-adaptive majority problems of large query size ⋮ Around Erdős-Lovász problem on colorings of non-uniform hypergraphs ⋮ A generalization of the Hajnal-Szemerédi theorem for uniform hypergraphs ⋮ The local cut lemma
Cites Work
This page was built for publication: Improved bounds and algorithms for hypergraph 2-coloring
