Strong edge colouring conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

In a finite simple graph $G$, an induced matching is a set of edges with disjoint endpoints and no edge joining endpoints of distinct members. A strong edge coloring partitions $E(G)$ into induced matchings. Let $s\chi'(G)$ be the smallest number of color classes and $\Delta=\Delta(G)$.

Statement recorded in the supplied source.

Must every $G$ satisfy \[s\chi'(G)\le\begin{cases}5\Delta^2/4,&\Delta\text{ even},\$5\Delta^2-2\Delta+1)/4,&\Delta\text{ odd}?\end{cases}\] The source also asks the stronger bipartite bound: if $G$ has bipartition $(A_1,A_2)$ with degrees at most $\Delta_i$ on $A_i$, is $s\chi'(G)\le\Delta_1\Delta_2$? In particular this would give $s\chi'(G)\le\Delta(G)^2$ for every bipartite graph. [S2]

Short English statement

Do strong edge colorings satisfy the sharp piecewise quadratic bound, and the stronger product-of-degrees bound for bipartite graphs?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3205 (OPG-46475). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Strong edge colouring conjecture, original node 46475, statement and mathematical discussion. https://www.openproblemgarden.org/op/strong_edge_colouring_conjecture.