Let \(x\) be a vertex of a graph \(G\). For \(r\ge0\), let \[ G_r=G\bigl[\{y\in V(G):d_G(x,y)=r\}\bigr] \] be the subgraph induced by the vertices at distance \(r\) from \(x\). Prove that \[ \chi(G)\le \max_r\bigl(\chi(G_r)+\chi(G_{r+1})\bigr). \]
Bound a graph's chromatic number using two consecutive distance layers
P-UNL852871-07A3
- Area
- Topology
- Seen at
- UNL
- Years
- 2007
- Status
- draft