Exact 2-distance b-coloring of some classes of graphs

Abstract

Given a graph $G$, the exact distance-p (or p-distance) graph $G^{[e p]}$ has $V(G)$ as its vertex set and two vertices are adjacent whenever the distance between them in $G$ equals $p$. An exact 2-distance coloring of a graph $G$ is a proper coloring of vertices of $G$ such that any two vertices which are at distance exactly 2 receive distinct colors. An exact 2-distance chromatic number of $G$ is the minimum $k$ for which $G$ admits an exact 2-distance coloring with $k$ colors. A b-coloring of a graph $G$ by $k$ colors is a proper $k$-vertex coloring such that in each color class, there exists a vertex adjacent to at least one vertex in every other color class. In this paper we introduce a new coloring called exact 2-distance b-coloring. It is a b-coloring of $G$ such that any two vertices at distance exactly 2 receive distinct colors and a graph $G$ is called exact 2-distance b-colorable graph if it admits such a coloring. An exact 2-distance b-chromatic number $\chi_{e 2 b}(G)$ of $G$ is the largest integer $k$ such that $G$ has an exact 2-distance b-coloring with $k$-colors. If each color class contains a vertex that has a 2-neighbour in all other color classes, such a vertex is called an exact 2-distance color dominating vertex. Some results based on exact 2-distance b-coloring are obtained. Exact 2-distance b-chromatic number of some classes of graphs are obtained.