Tight bounds for the N2-chromatic number of graphs
Abstract
Let G be a connected graph. A vertex coloring of G is an N2-vertex coloring if, for every vertex v, the number of different colors assigned to the vertices adjacent to v is at most two. The N2-chromatic number of G is the maximum number of colors that can be used in an N2vertex coloring of G. In this paper, we establish tight bounds for the N2-chromatic number of a graph in terms of its maximum degree and its diameter, and characterize those graphs that attain these bounds.
This paper has been withdrawn.
