On some properties of suboptimal colorings of graphs
Ivo Blöchliger, D. de Werra · Networks · 2004
Abstract Starting from the trivial observation that, in any optimal coloring of a graph, there always exists a node v such that its neighborhood N(v) contains all colors, we examine related properties in suboptimal colorings (i.e., those using more than χ(G) colors, where χ(G) is the chromatic number). In particular, we show that, in any (χ(G) + p)‐coloring of G, there is a node v such that its generalized neighborhood Nq(v) with q = max{2p − 1, 2} contains χ(G) colors for p ≥ 1. Additional properties of (χ(G) + p)‐colorings are also given. © 2004 Wiley Periodicals, Inc.