<p>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}$.</p>

<p>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 </p>

<p><strong>EDIT 1:</strong> 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$.</p>

<p>Links to related literature will be helpful.</p>

<p>Thanks in advance!</p>

CC BY-SA 3.0
2014-03-26T06:14:21.330Z
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
CC BY-SA 3.0
2014-03-26T06:26:32.307Z
@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
CC BY-SA 3.0
2014-03-26T14:41:55.110Z
In Jim's example $k = 1$. Sounds very unlikely you'd be able to say anything.
Sasho Nikolov
CC BY-SA 3.0
2014-03-26T15:35:37.057Z
@SashoNikolov: Thanks for the exposition :). I have added an edit to remove such trivial cases.
Vivek Bagaria
CC BY-SA 3.0
2014-03-27T02:18:52.863Z
Your edit introduced an incomplete sentence and I don't see how it removes these cases? Also things like densely connected neighborhoods suggest high chromatic number, not upper bounds.
Sasho Nikolov
CC BY-SA 3.0
2014-03-27T17:58:04.293Z
@SashoNikolov: I added the phrase lots of cycles. By which i mean that let it have lots of cycles of any length containing vertex v. I was not very clear.
Vivek Bagaria
<reference-request><graph-theory><graph-isomorphism><graph-colouring>
Chromatic number of a graph where neighbourhood of each vertex is isomorphic
Vivek Bagaria
# Chromatic number of a graph where neighbourhood of each vertex is isomorphic

(Asked by: username_0 on 2014-03-26)

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$.

Links to related literature will be helpful.

Thanks in advance!

**Tags:** reference-request, graph-theory, graph-isomorphism, graph-colouring
> **Comments:**
> **username_1**: 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.  
> **username_0**: @JimNastos: The chromatic number of$G_{v_i}$ is given to be $k$. Using $k$ can we characterize the chromatic number of the graph?  
> **username_2**: In Jim's example $k = 1$. Sounds very unlikely you'd be able to say anything.  
> **username_0**: @SashoNikolov: Thanks for the exposition :). I have added an edit to remove such trivial cases.  
> **username_2**: Your edit introduced an incomplete sentence and I don't see how it removes these cases? Also things like densely connected neighborhoods suggest high chromatic number, not upper bounds.  
> **username_0**: @SashoNikolov: I added the phrase lots of cycles. By which i mean that let it have lots of cycles of any length containing vertex v. I was not very clear.  

---

## 0 answers

