COLORED-INDEPENDENCE ON BIPARTITE GRAPHS
Sarah Lange, Michael Terhaar, Anne Sinko · 2011
Colored-independence is a storage/scheduling problem which, in addition to the standard restriction involving pairs of elements that cannot be placed together, considers sets of elements that must be placed together. A set S is a colored-independent set if, for each color class Vi, S ∩ Vi = Vi or S ∩ Vi = ∅. Results for the independence-partition number, βPRT (G), and the lower independence-partition number, iPRT (G), for a variety of families will be presented, including paths, cycles, grids, and a characterization of bipartite graphs that achieve iPRT (T ) = |V1| where V1 is the smaller of the bipartition sets of graph G. Restrictions placed on the size of each Vi will also be considered, particularly βcpl(G) where for each Vi, |Vi| ≤ 2.