No-hole 2-distant colorings (Q1310246)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | No-hole 2-distant colorings |
scientific article |
Statements
No-hole 2-distant colorings (English)
0 references
2 January 1994
0 references
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.
0 references
coloring
0 references
channel assignment problem
0 references