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: