Skip to main content
added 71 characters in body
Source Link

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?

EDIT: Will ask about Hadwiger number in different post, it's better to ask one question per post.

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?

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?

EDIT: Will ask about Hadwiger number in different post, it's better to ask one question per post.

Source Link

"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?