On the simultaneous edge-coloring conjecture
Let \(S = \{s_1,\dots, s_m, t_1,\dots, t_n\}\) be a positive integer sequence. The sequence \(S\) is called a bipartite graphic sequence if there is a bipartite graph \(G\) with bipartition \(\{ X, Y \}\) such that \(\{ d(x_1) , \dots , d(x_m) \} = \{ s_1, \dots , s_m \},\) and \(\{ d(y_1) , \dots , d(y_n) \} = \{ t_1, \dots , t_n \}\) where \(X = \{ x_1 , \dots , x_m \} \) and \(Y = \{ y_1 , \dots , y_n \}\) and \(d(v)\) is the degree of vertex \(v\); the graph \(G\) is called a realization of \(S\). It was conjectured by Keedwell (1993) and reproposed by Cameron (1999) that every bipartite graphic sequence \(S\) with minimum degree \(\delta(S) \geq 2\) has a realization \(G\) of \(S\) such that \(G\) has two proper edge-colorings with the following properties: (1) for any vertex, the set of colors appearing on edges at that vertex are the same in both colorings; (2) no edge receives the same color in both colorings. The conjecture was originally motivated by studies of critical partial Latin squares (Keedwell 1993). It is proved in this paper that the conjecture is true for bipartite graphic sequences \(S\) with \(\delta(S) \geq 4\). Note that the conjecture was solved by Luo, Zang and the reviewer recently.
scientific article; zbMATH DE number 1455615
scientific article