Originator(s): N. Alon, M. Saks, P.D. Seymour
Definitions:
Conjecture/Question: Every union of m pairwise edge-disjoint complete bipartite graphs is (m+1)-colorable.
Background/motivation: This statement is a bipartite analogue of the Erdos-Faber-Lov\'asz Conjecture. A special case of it would be the Graham-Pollak Theorem stating that the minimum number of complete bipartite subgraphs needed to decompose Kn is n-1. Algebraic proofs of this theorem are known, but no purely combinatorial proofs are known.
Comments/Partial results:
References:
Graham R.L. and Pollak H.O. On embedding graphs in squashed cubes. Graph
theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich.,
1972; dedicated to the memory of J. W. T. Youngs), pp. 99--110. Lecture Notes
in Math., Vol. 303, Springer, Berlin, 1972.