{"id":"arxiv/2603.15207","url":"https://arxiv.org/abs/2603.15207","tags":["math.CO","cs.DM"],"score":0,"title":"The strong chromatic index of $K_{t,t}$-free graphs","domain":"math.CO","source":"arxiv","authors":["Richard Bi","Peter Bradshaw","Abhishek Dhawan","Jingwei Xu"],"reviews":0,"subject":"math.CO","summary":"A strong edge coloring of a graph $G$ is an edge coloring $φ\\,:\\,E(G) \\rightarrow \\mathbb N$ such that each color class forms an induced matching in $G$. The strong chromatic index of $G$, written $χ'_s(G)$, is the minimum number of colors needed for a strong edge coloring of $G$. Erdős and Nešetřil conjectured in 1985 that if $G$ has maximum degree $d$, then $χ'_s(G) \\leq \\frac 54 d^2$. Mahdian showed in 2000 that if $G$ is $C_4$-free, then $χ'_s(G) \\leq (2+o(1)) \\frac{d^2}{\\log d}$, and he conjectured that the same upper bound holds for $K_{t,t}$-free graphs. In this paper, we prove this…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-16","reactions":{}}