On the simultaneous edge-coloring conjecture

DOI10.1016/S0012-365X(99)00353-2MaRDI QIDQ1567288zbMATH OpenOpenAlexWikidataFDO

Authors M. T. Hajiaghaee, R. Tusserkani, E. S. Mahmoodian, Vahab S. Mirrokni, Amin Saberi

Publication date 28 November 2001

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)00353-2

zbMATH Keywords

graphic sequencepartial Latin squaresimultaneous edge-colorings

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Review text

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.

Recommendations

• On a conjecture of Keedwell and the cycle double cover conjecture
• Nowhere-zero 4-flows; simultaneous edge-colorings; and critical partial Latin squares
• Bipartite-assembly
• Ramsey Problems with Bounded Degree Spread
• scientific article; zbMATH DE number 2192182
• On the simultaneous edge coloring of graphs
• A sufficient condition for a pair of sequences to be bipartite graphic
• scientific article; zbMATH DE number 1294016
• Constructing a bipartite graph of maximum connectivity with prescribed degrees
• On the edge colouring of bipartite graphs

Cited in

(9)

• Maximum genus of strong embeddings
• On a conjecture of Keedwell and the cycle double cover conjecture
• Constructing and deconstructing Latin trades
• Nowhere-zero 4-flows; simultaneous edge-colorings; and critical partial Latin squares
• On the simultaneous edge coloring of graphs
• scientific article; zbMATH DE number 30752 (Why is no real title available?)
• scientific article; zbMATH DE number 913024 (Why is no real title available?)
• On the volume of -way G-trade
• On the volume of \(\mu\)-way \(S(K_{1,3})\)-trade on \((3, 6)\)-fullerene graphs

This page was built for publication: On the simultaneous edge-coloring conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1567288)