β Scribed by Shaoji Xu
No coin nor oath required. For personal study only.
Xu, S., The chromatic uniqueness of complete bipartite graphs, Discrete Mathematics 94 (1991) 153-159. This paper is partitioned into two parts. In the first part we determine the maximum number of induced complete bipartite subgraphs in graphs with some given conditions. Using a theorem given in the first part, we prove the conjecture raised in (1982) that K(m, n) is chromatically unique when m 3 n 3 2.
π SIMILAR VOLUMES
We prove the chromatic uniqueness of the following infinite families of bipartite graphs: Km,,,+k, l~rt3K,,,,,,,+k, with m~>2 and 0~ 3, where K~,,, denote the graph obtained from K,,,n by deleting one edge. As a particular case we prove a conjecture made by C.Y. Chao in
## Abstract Let __K(p, q), p β€ q__, denote the complete bipartite graph in which the two partite sets consist of __p__ and __q__ vertices, respectively. In this paper, we prove that (1) the graph __K(p, q)__ is chromatically unique if __p__ β₯ 2; and (2) the graph __K(p, q)__ β __e__ obtained by del
## Abstract A graph is chromatically unique if it is uniquely determined by its chromatic polynomial. Let __G__ be a chromatically unique graph and let __K__~__m__~ denote the complete graph on __m__ vertices. This paper is mainly concerned with the chromaticity of __K__~__m__~ + __G__ where + deno