Abstract: A set of vertices S
is a neighborhood set of a graph if The nomatic number of a graph is the maximum number k,
such that V can be partitioned into k
disjoint neighborhood sets. The main purpose of this paper is to give linear
algorithm for the nomatic number problem in interval graphs. We also prove that for any interval graph G,
where is the minimum degree of a vertex
in G.
Keywords and phrases: neighborhood set, nomatic number, interval graph, degree, linear algorithm.
