Chromatic uniqueness of certain bipartite graphs.

*(English)*Zbl 0862.05045All 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.

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 |