Conflict-free coloring with respect to a subset of intervals

2013 IJRSC – Volume 2 Issue 2


Singhal, Vinay*
Meerut Institute of Engineering & Technology, Meerut, India (

Rastogi, Akanksha
Meerut Institute of Engineering & Technology, Meerut, India (


Given a hypergraph H = (V, E), a coloring of its vertices is said to be conflict-free if for every hyperedge S ∈ E there is at least one vertex in S whose color is distinct from the colors of all other vertices in S. The discrete interval hypergraph Hn is the hypergraph with vertex set {1, . . . , n} and hyperedge set the family of all subsets of consecutive integers in {1, . . . , n}. We provide an algorithm for conflict-free coloring any subhypergraph of Hn. i.e. any subset of possible intervals. If in this hypergraph, the hyperedge have 1n number of vertices then we show that the algorithm uses at most ⌊1n/2⌋ colors and we prove that our analysis is tight.

Keywords: frequency-assignment problem; cellular network; conflict-free coloring; intervals; subset of intervals; fully-covered algorithm



*Corresponding Author