# zbMATH — the first resource for mathematics

Chromatic uniqueness of certain bipartite graphs. (English) Zbl 0862.05045
All graphs considered here are simple graphs. The chromatic polynomial of a graph $$X$$ will be denoted by $$P_X (\lambda)$$. Two graphs $$X$$ and $$Y$$ are chromatically equivalent (or $$\chi$$-equivalent) if they have the same chromatic polynomial. A graph $$X$$ is chromatically unique $$(\chi$$-unique) if $$X$$ is isomorphic to every graph which is $$\chi$$-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\leq n$$. We prove that if $$G$$ is obtained from $$K_{m,m}$$ or $$K_{m,m+1}$$ by deleting $$d$$ disjoint edges, $$0\leq d \leq 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 [K. M. Koh and K. L. Teo, Graphs Comb. 6, No. 3, 259-285 (1990; Zbl 0727.05023)], of determining the $$\chi$$-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\geq 2$$, the graphs obtained from $$K_{m, m+k}$$ by removing any two of its edges are $$\chi$$-unique if $$m$$ is large enough.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
##### Keywords:
chromatic polynomial; bipartite graphs