$G$.

We refer to [@bondy1991] for a survey of reconstruction problems.

The chromatic polynomial and the $\mathcal{N}$-matrix
-----------------------------------------------------

Stronger reconstruction results on the chromatic polynomial were implicit in Whitney’s work [@whitney1932], although Ulam’s conjecture had not been posed at the time. Motivation for some of the work presented in this paper comes from Whitney’s work on the chromatic polynomials. The discussion of the chromatic polynomial presented here is based on [@biggs1993].

A graph $G$ is called [*quasi-separable*]{} if there exists $K\subsetneq VG$ such that $G_K$ is a complete graph and $G-K$ is disconnected. If $|K| \leq 1$ then $G$ is said to be separable.

(Theorem 12.5 in [@biggs1993]) \[thm-biggs\] The chromatic polynomial of a graph is determined by its proper induced subgraphs that are not quasi-separable.

The procedure of computing the chromatic polynomial may be outlined as follows. First a matrix $\mathcal{N}(G) = (N_{ij})$ is constructed. The rows and the columns of $\mathcal{N}(G)$ are indexed by induced subgraphs $\Lambda_1, \Lambda_2, \ldots , \Lambda_I = G$, which are the distinct isomorphism types of non-quasi-separable induced subgraphs of $G$. The list includes $K_1 = \Lambda_1$ and $K_2=\Lambda_2$. The indexing graphs are ordered in such a way that $v(\Lambda_i)$ are in non-decreasing order. 