Loading...

On the simultaneous edge-coloring conjecture

Hajiaghaee, M. T ; Sharif University of Technology | 2000

3102 Viewed
  1. Type of Document: Article
  2. DOI: 10.1016/S0012-365X(99)00353-2
  3. Publisher: Elsevier , 2000
  4. Abstract:
  5. At the 16th British Combinatorial Conference (1997), Cameron introduced a new concept called 2-simultaneous edge-coloring and conjectured that every bipartite graphic sequence, with all degrees at least 2, has a 2-simultaneous edge-colorable realization. In fact, this conjecture is a reformulation of a conjecture of Keedwell (Graph Theory, Combinatorics, Algorithms and Applications, Proceedings of Third China-USA International Conference, Beijing, June 1-5, 1993, World Scientific Publ. Co., Singapore, 1994, pp. 111-124) on the existence of critical partial latin squares (CPLS) of a given type. In this paper, using some classical results about nowhere-zero 4-flows and oriented cycle double covers, we prove that this conjecture is true for all bipartite graphic sequences with all degrees at least 4. © 2000 Elsevier Science B.V. All rights reserved
  6. Keywords:
  8. Source: Discrete Mathematics ; Volume 216, Issue 1-3 , 2000 , Pages 267-272 ; 0012365X (ISSN)
  9. URL: https://www.sciencedirect.com/science/article/pii/S0012365X99003532