Star-In-Coloring of Benzenoid Graphs And Grid Graphs.

Abstract

In this paper, we obtained the general pattern of star-in-coloring introduced by Sudha et al.[6] for benzenoid graphs which belong to the series of coronene or circumcoronene graphs and found that its star-in-coloring chromatic number is always 4. We have also obtained the star-in-coloring of grid of squares by considering the cartesian product of two paths and found its chromatic number as 5.

We have introduced two new definitions for grid of diamonds and grid of hexagons and found the chromatic number of star-in-coloring of Sudha's grid of complete diamonds and Sudha's grid of complete hexagons to be 5 and 4 respectively.

The tensor product of two paths  and  for all  and , in general, with the conditions in our definition give rise to the graph of diamonds with some additional edges. We discussed the star-in-coloring of this graph and found its star-in-coloring chromatic number as 5 for all values of and .

Likewise the strong product of two paths  and  for all  and  with the conditions in our definition give rise to the graph of hexagons with some additional edges. The star-in-coloring of this type of graphs is also discussed and found its star-in-coloring chromatic number as 4 for all  and .