1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

The chromatic polynomial, and therefore the chromatic number, was proved reconstructible by Tutte in his famous paper "All the king's horses". I don't know about the Hadwiger number.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I am desperatly searching for a pdf of that article ( or alternatively that of the proceedings "Graph Theory and Related Topics" . Any idea ? $\endgroup$
    – Jérôme JEAN-CHARLES
    Commented Dec 21, 2023 at 12:05
  • $\begingroup$ @JérômeJEAN-CHARLES You can read the conference proceedings here if you register for a free account. You can also write to me ([email protected]) for a copy of the original Waterloo technical report. $\endgroup$
    – Brendan McKay
    Commented Dec 21, 2023 at 22:22
  • $\begingroup$ Ok thank you I mail you. $\endgroup$
    – Jérôme JEAN-CHARLES
    Commented Dec 23, 2023 at 19:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .