On the simultaneous edge-coloring conjecture
type: Item
instance of: scholarly article
title: On the simultaneous edge-coloring conjecture
zbMATH Open document ID: 0973.05029
DOI: 10.1016/S0012-365X(99)00353-2
author: M. T. Hajiaghaee
author: R. Tusserkani
author: E. S. Mahmoodian
author: Vahab S. Mirrokni
author: Amin Saberi
published in: Discrete Mathematics
publication date: 2001-11-28T00:00:00Z
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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05B15
zbMATH DE Number: 1455615
zbMATH Keywords: simultaneous edge-colorings
zbMATH Keywords: partial Latin square
zbMATH Keywords: graphic sequence
MaRDI profile type: Publication
Wikidata QID: Q123266652
full work available at URL: s0012-365x(99)00353-2
OpenAlex ID: W2048980622
Recommended article: On a conjecture of Keedwell and the cycle double cover conjecture
Recommended article: Nowhere-zero 4-flows; simultaneous edge-colorings; and critical partial Latin squares
Recommended article: Q3512799
Recommended article: Ramsey Problems with Bounded Degree Spread
Recommended article: Q5463558
Recommended article: On the simultaneous edge coloring of graphs
Recommended article: A SUFFICIENT CONDITION FOR A PAIR OF SEQUENCES TO BE BIPARTITE GRAPHIC
Recommended article: Q4246280
Recommended article: Constructing a bipartite graph of maximum connectivity with prescribed degrees
Recommended article: On the edge colouring of bipartite graphs
description: scientific article; zbMATH DE number 1455615