The \(k\) -Strong Conflict-Free ( \(k\) -SCF colouring problem seeks to find a colouring of the vertices of a hypergraph \(H\) using minimum number of colours so that in every hyperedge \(e\) of \(H\) , there are at least \(\min\{|e|,k\}\) vertices whose colours are different from that of all other vertices in \(e\) . In the case of interval hypergraphs, we present an exact \({\mathsf{P}}\) -time algorithm for the \(k\) -SCF problem thus solving an open problem posed in 2014. We achieve our results by showing that for any hypergraph, a \(k\) -SCF colouring is a proper colouring of a related simple graph which we refer to as a co-occurrence graph . We then show that a co-occurrence graph is obtained by identifying an induced subgraph of a second simple graph that we introduce, which we refer to as the conflict graph . For interval hypergraphs, we show that each co-occurrence graph and the conflict graph are perfect graphs. This property plays a crucial role in our polynomial time algorithm. Second, we show that for an interval hypergraph, the \(1\) -SCF colouring number is the minimum partition of its intervals into sets such that each set has an exact hitting set (a hitting set in which each interval is hit exactly once).

Given a hypergraph H, the conflict-free colouring problem is to colour vertices of H using minimum colours so that in every hyperedge e of H, there is a vertex whose colour is different from that of all other vertices in e. Our results are on a variant of the conflict-free colouring problem considered by Cheilaris et al.[Cheilaris et al., 2014], known as the 1-Strong Conflict-Free (1-SCF) colouring problem, for which they presented a polynomial time 2-approximation algorithm for interval hypergraphs. We show that an optimum 1-SCF colouring for interval hypergraphs can be computed in polynomial time. Our results are obtained by considering a different view of conflict-free colouring which we believe could be useful in general. For interval hypergraphs, this different view brings a connection to the theory of perfect graphs which is useful in coming up with an LP formulation to select the vertices that could be coloured to obtain an optimum conflict-free colouring. The perfect graph connection again plays a crucial role in finding a minimum colouring for the vertices selected by the LP formulation.