No-hole 2-distant colorings (Q1310246): Difference between revisions

A variant of graph coloring which is motivated by the channel assignment problem is introduced. This variant is called no-hole 2-distant coloring which is meant 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). The question of what graphs have such colorings is investigated. Further, 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 is also studied.