Skip to main content
1 of 2

"Reduce-by-1"-isomorphic graphs

Let $G, H$ be two finite, simple, undirected graphs. We call them "reduce-by-1"-isomorphic, or $r_1$-isomorphic for short, if there is a bijection $\psi: V(G) \to V(H)$ such that for all $v \in V(G)$ we have that $G \setminus \{v\}$ is isomorphic to $H \setminus \{\psi(v)\}$.

(Ulam's reconstruction conjecture, or some version of it, states that $r_1$-isomorphic implies isomorphic.)

Can we prove that if $G, H$ are $r_1$-isomorphic then they have the same chromatic number and the same Hadwiger number?