On the chromatic uniqueness of certain bipartite graphs (Q1182976): Difference between revisions

A graph \(G\) is chromatically unique if any other graph with the same chromatic polynomial is isomorphic to \(G\). For example, it is known that the complete bipartite graph \(K(n,m)\) is chromatically unique provided \(n,m\geq 2\), as is the complete graph minus a single edge \(K^{-1}(n,m)\) provided \(n,m\geq 3\). In this paper the author extends the investigation into the chromatic uniqueness of complete bipartite graphs minus 2, 3, or 4 edges. Let \(K^{-r}(n,m)\) denote the class of complete bipartite graphs \(K(n,m)\) with \(r\) edges removed. There are 3 graphs in \(K^{-r}(n,m)\) when \(r=2\), 6 graphs when \(r=3\), and 16 graphs for \(r=4\). The author derives a sufficient condition for a graph in \(K^{-2}(n,m)\) to be chromatically unique. In particular, each such graph is chromatically unique when \(| n-m|\leq 3\). Moreover, graphs with \(| n-m|=d\) are chromatically unique provided that \(n\) is sufficiently large (an explicit polynomial bound is given). In the class \(K^{-3}(m,m)\) any member is chromatically unique provided \(| n-m|\leq 1\) (with a few small exceptions). In \(K^{-4}(n,m)\) any graph is chromatically unique provided \(n=m\geq 4\). Also, each graph in \(K^{-4}(n,n+1)\) is chromatically unique for \(n\geq 5\). A few other results of a similar nature are presented.