A Note on the Alon-Saks-Seymour Coloring Conjecture

Abstract

Kahn (see [3]) reported that N. Alon, M. Saks, and P. D. Seymour made the following conjecture. If the edge set of a graph \(G\) is the disjoint union of the edge sets of \(m\) complete bipartite graphs, then \(\chi(G) \leq m+1\). The purpose of this paper is to provide a proof of this conjecture for \(m \leq 4\) and \(m \geq n – 3\) where \(G\) has \(n\) vertices.