In this paper, we introduce a variant of graph coloring which is motivated by the channel assignment problem. In this variant, called no-hole 2-distant coloring, we seek to color the vertices of a graph with positive integers so that two adjacent vertices get integers which differ by more than 1 (the 2-distant requirement) and so that the set of integers used as colors is a consecutive set (the no-hole requirement). We study the question of what graphs have such colorings. We also study the question of what graphs have such colorings which are near-optimal in the sense that the span, or separation between the largest and smallest colors used, is no more than one larger than the minimum span in a non-adjacent coloring which may have holes.
All Science Journal Classification (ASJC) codes
- Modeling and Simulation
- Computer Science Applications