14 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)139-144
Number of pages6
JournalMathematical and Computer Modelling
Volume17
Issue number11
DOIs
StatePublished - Jun 1993

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Computer Science Applications

Fingerprint Dive into the research topics of 'No-hole 2-distant colorings'. Together they form a unique fingerprint.

  • Cite this