Modular Coloring and Switching in Some Planar Graphs

Abstract

For a connected graph G, let c: V (G) →ℤk (k ≥ 2) be a vertex coloring of G. The color sum \sigma(v) of a vertex v of G is defined as the sum in ℤk of the colors of the vertices in N (v) that is (v) = \sum_{u\inN(v)}{c(u)} (mod k). The coloring c is called a modular k-coloring of G if ????(x) ≠ ????(y) in ℤk for all pairs of adjacent vertices x, y \in\ G. The modular chromatic number or simply the mc-number of G is the minimum k for which G has a modular k-coloring. A switching graph is an ordinary graph with switches. For many problems, switching graphs are a remarkable straight forward and natural model, but they have hardly been studied. A vertex switching Gv of a graph G is obtained by taking a vertex V of G, removing the entire edges incident with V and adding edges joining V to every vertex which are not adjacent to V in G. In this paper we determine the modular chromatic number of Wheel graph, Friendship graph and Gear graph after switching on certain vertices. Here, we first define switching of graphs. Next, we investigating several problems on finding the mc(G) after switching of graphs and provide their characterization in terms of complexity.