On monochromatic spectra in graphs

Abstract

For a nontrivial connected graph G, let c: V(G) → ℤ<inf>2</inf> be a vertex coloring of G where c(v) ≈ 0 for at least one vertex v of G. Then the coloring c induces a new coloring σ: V(G) → ℤ<inf>2</inf> of G defined by σ (v) = Σ<inf>u∞N[v]</inf> c(u) where N[v] is the closed neighborhood of v and addition is performed in ℤ<inf>2</inf>. If σ(v) = 0 ∞ ℤ<inf>2</inf> for every vertex v in G, then the coloring c is called a (modular) monochromatic (2,0)-coloring of G. A graph G having a monochromatic (2,0)-coloring is a (monochromatic) (2,0)-colorable graph. The minimum number of vertices colored 1 in a monochromatic (2,0)-coloring of G is the (2,0)-chromatic number of G and is denoted by χ(2,0)(G). For a (2,0)-colorable graph G, the monochromatic (2,0)-spectrum S<inf>(2,0)</inf> (G) of G is the set of all positive integers k for which exactly k vertices of G can be colored 1 in a monochromatic (2,0)-coloring of G. Monochromatic (2,0)-spectra are determined for several well-known classes of graphs. If G is a connected graph of order n ≥ 2 and a ∞ S<inf>(2,0)</inf>(G), then o is even and 1 ≤ |S<inf>(2,0)</inf>(G)| ≤ | n/2]. It is shown that for every pair k, n of integers with 1 ≤ k ≤ [n/2], there is a connected graph G of order n such that |S<inf>(2,0)</inf>(G)| = k. A set S of positive even integers is (2,0)-realizable if S is the monochromatic (2,0)-spectrum of some connected graph. Although there are infinitely many non-(2,0)-realizable sets, it is shown that every set of positive even integers is a subset of some (2,0)-realizable set. Other results and questions are also presented on (2,0)-realizable sets in graphs.