# Chromatic number of a graph where neighbourhood of each vertex is isomorphic

Consider a graph $G(V,E)$. For any two vertices $v_1 , v_2 \in V$, the subgraph induced by the neigbourhood of vertex $v_1$, denoted by $G_{v_1}$ be isomorphic to the subgraph induced by the neigbourhood of veretx $v_2$, denoted by $G_{v_2}$.

Now suppose one can color $G_{v_1}$(and $G_{v_2}$) using $k$ colors. Can one upper-bound the chromatic number of the graph $G$ in terms of $k$ (and other graph

EDIT 1: The motivation behind this question is the fact that the chromatic number is upper bounded by max degree of the graph. Therefore it might happen that if the neighbourhood satisfies certain properties (like densely connected?,lot of cycles of all lengths?), may be one can related its chromatic number of graph $G$ to $k$.

• If $G$ is a triangle-free graph, the neighbourhood graph $G_{v_i}$ for every $v_i$ is a stable set, yet the chromatic number is still very hard to characterize for triangle-free graphs in general. – JimN Mar 26 '14 at 6:14
• @JimNastos: The chromatic number of$G_{v_i}$ is given to be $k$. Using $k$ can we characterize the chromatic number of the graph? – Vivek Bagaria Mar 26 '14 at 6:26
• In Jim's example $k = 1$. Sounds very unlikely you'd be able to say anything. – Sasho Nikolov Mar 26 '14 at 14:41