pipette
ESEspañol

The Brualdi--Quinn conjecture on strong edge-coloring holds fractionally and asymptotically

Rong Luo, Gexin Yu, Xiangqian Zhou

Preprint

In the authors' words

Let be a bipartite graph with parts and , and let and be the maximum degrees of the vertices in and in , respectively. Brualdi and Quinn conjectured that the strong chromatic index of is at most . We prove that the fractional strong chromatic index of is at most , and that the conjecture holds asymptotically: as . The error term is with . Both results rest on a smart partition of edges and Lov\'asz Local Lemma.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 8 pages. Comments are welcome