Allocation of Shared Resources with Bounded Conflicts Over Unit and Laminar Interval Graphs

This paper addresses the challenge of shared resource allocation in the presence of limited resources, making collaboration or resource sharing a necessity. The problem of allocating shared resources is modeled by representing conflicts among agents located on a social graph G and we aim to allocate shared resources such that the conflicts among agents are bounded by a predefined threshold t. This problem is commonly referred to as defective coloring in graph theory. While defective coloring is NP-hard for general graphs, it can be solved in polynomial time for certain classes of structured graphs. This paper proposes polynomial-time algorithms for defective coloring on unit and laminar interval graphs. Specifically, we present a better polynomial-time algorithm for defective coloring on unit interval graphs that uses at most \(\lceil \frac{\omega (G)}{t+1} \rceil + 1\) colors, where \(\omega (G)\) denotes the maximum clique size of the graph G. We also demonstrate that our algorithm requires fewer or an equal number of colors compared to existing approaches. While for a unit interval graph, the number of colors is inversely proportional to the allowed defects (t), we show that for general interval graphs, one might require \(\omega (G)\) colors independent of the value of t. We then propose a linear-time greedy algorithm for laminar interval graphs (a subclass of interval graphs) and show the optimality of the proposed algorithm. This algorithm marks a significant advancement in the theory of defective coloring and opens new avenues for efficient algorithms in interval graph classes.