id: 00975328 dt: j an: 00975328 au: Giudici, Reinaldo E.; Lima de Sá, Eduardo ti: Chromatic uniqueness of certain bipartite graphs. so: Congr. Numerantium 76, 69-75 (1990). py: 1990 pu: Utilitas Mathematica Publishing Inc., Winnipeg la: EN cc: ut: chromatic polynomial; bipartite graphs ci: Zbl 0727.05023 li: ab: All graphs considered here are simple graphs. The chromatic polynomial of a graph $X$ will be denoted by $P_X (λ)$. Two graphs $X$ and $Y$ are chromatically equivalent (or $χ$-equivalent) if they have the same chromatic polynomial. A graph $X$ is chromatically unique $(χ$-unique) if $X$ is isomorphic to every graph which is $χ$-equivalent to $X$. We shall be concerned with bipartite graphs, i.e., graphs whose vertex set can be partitioned into two subsets $H_1$, $H_2$ such that every edge of the graph joints $H_1$ with $H_2$. We will denote by $K_{m,n}$ the complete bipartite graph for which $H_1$ has $m$ vertices and $H_2$ has $n$ and, in general will assume $m\le n$. We prove that if $G$ is obtained from $K_{m,m}$ or $K_{m,m+1}$ by deleting $d$ disjoint edges, $0\le d \le m$ and $m>2$, then $G$ is chromatically unique; the cases $d=0$ and $d=1$ were known. The case $d=2$ gives a partial answer to Problem 12 stated in [{\it K. M. Koh} and {\it K. L. Teo}, Graphs Comb. 6, No. 3, 259-285 (1990; Zbl 0727.05023)], of determining the $χ$-uniqueness of graphs obtained from the complete $K_{m,n}$ graph by removing two of its edges; in fact, we prove that a graph obtained in this way from $K_{m,m}$ or $K_{m,m+1}$ is chromatically unique. We also prove that for each $k\ge 2$, the graphs obtained from $K_{m, m+k}$ by removing any two of its edges are $χ$-unique if $m$ is large enough. rv: