Premium
The chromaticity of complete bipartite graphs with at most one edge deleted
Author(s) -
Teo C. P.,
Koh K. M.
Publication year - 1990
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190140110
Subject(s) - combinatorics , bipartite graph , mathematics , complete bipartite graph , chromaticity , graph , discrete mathematics , computer science , artificial intelligence
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 deleting an edge e from K(p, q) is chromatically unique if p ≥ 3. The first result was conjectured by Salzberg, López, and Giudici, who also proved the second result under the condition that q ‐ p ≤ 1.