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!

  • 4
    $\begingroup$ 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. $\endgroup$ – JimN Mar 26 '14 at 6:14
  • $\begingroup$ @JimNastos: The chromatic number of$G_{v_i}$ is given to be $k$. Using $k$ can we characterize the chromatic number of the graph? $\endgroup$ – Vivek Bagaria Mar 26 '14 at 6:26
  • 2
    $\begingroup$ In Jim's example $k = 1$. Sounds very unlikely you'd be able to say anything. $\endgroup$ – Sasho Nikolov Mar 26 '14 at 14:41
  • $\begingroup$ @SashoNikolov: Thanks for the exposition :). I have added an edit to remove such trivial cases. $\endgroup$ – Vivek Bagaria Mar 26 '14 at 15:35
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Mar 27 '14 at 2:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.