Discrete Lunch‎ > ‎

Aril 20: Hypergraph recoloring

posted Apr 20, 2015, 2:05 AM by Dirk Oliver Theis   [ updated Apr 24, 2015, 3:30 AM ]
An assignment of one of two colors, red or blue, to every vertex of a hypergraph is called a proper 2-coloring, if no edge is monochromatic. Hypergraphs which have a proper 2-coloring are sometimes said to have Property B (as in "bipartite", maybe?).
Unlike for usual graphs, where deciding whether it is bipartite can easily done in polynomial time, deciding whether a given hypergraph has a proper 2-coloring is an NP-complete problem.
In today's Discrete Lunch, we'll discuss a smart re-coloring procedure, which finds a proper 2-coloring for every r-uniform hypergraph which does not have too many edges.