2-DISTANCE STRONG B-COLORING OF PATHS AND CYCLES

A 2-distance coloring and b-coloring are two independent types of vertex coloring of graphs. When 2-distance coloring demands that vertices at distance at most 2 must receive distinct colors, the b-coloring demands that in the vertex coloring, each color class must contain a vertex having a neighbor in every other color class. The first combination of these two types of coloring is 2-distance b-coloring. It is a 2-distance coloring in which every color class contains a vertex which has a neighbor in every other color class. In this coloring, for a vertex u, vertices at distance at most 2 from u are considered and given distinct colors. If the at most 2 condition on neighbors is given to the neighboring condition on b-coloring, a new coloring can be obtained. In this paper, the new coloring, a second combination of the two types of coloring is introduced. This coloring is called 2-distance strong b-coloring (2sb-coloring). It is a 2-distance coloring in which every color class contains a vertex u such that there is a vertex v in every other color class satisfying the condition that distance between u and v is less than or equal to 2. The 2-distance strong b-chromatic number χ 2sb(G) (2sbnumber) is the maximum k such that G admits a 2sb-coloring with k colors. In this paper, the exact bound of the 2sb-number of paths and cycles are obtained.