---

Claim. For every $\varepsilon>0$ there is $\Delta_0$ such that every graph $G$ with no cycle of length four and maximum degree $\Delta\ge\Delta_0$ has

$$\mathrm{sq}(G)\le(2+\varepsilon)\frac{\Delta^2}{\log\Delta},$$

a bound sharp up to the constant factor. The result is Mahdian's, in his M.Sc. thesis The strong chromatic index of graphs (University of Toronto, 2000; the site's thread links the University of Toronto repository copy, linked above) and in M. Mahdian, The strong chromatic index of $C_4$-free graphs, Random Structures Algorithms 17 (2000), no. 3--4, 357--375 (the Crossref record dates the issue October 2000, whose nominal first day is this page's date). The site's commentary credits the thesis. For $\Delta$ large enough that $(2+\varepsilon)\Delta^2/\log\Delta\le\frac54\Delta^2$, the bound of Problem 149 holds for these graphs.

Covers. Every $C_4$-free graph whose maximum degree is at least the threshold $\Delta_0$ of the theorem, which the statement does not make explicit. It says nothing about graphs containing a four-cycle, among them the blown-up five-cycles that make the conjectured constant sharp, nor about $C_4$-free graphs of small maximum degree.

Depends on. Nothing in this wiki.

Acceptance. Refereed: Random Structures Algorithms 17 (2000), no. 3--4, 357--375. The statement recorded above is the one the thesis gives in its University of Toronto repository abstract: $(2+o(1))\Delta^2/\ln\Delta$ for $C_4$-free graphs, which the abstract says implies the conjecture for $C_4$-free graphs of large maximum degree. The zbMATH review of the journal paper (Zbl 0961.05022) describes the same result: an asymptotically better bound for graphs without a four-cycle, best possible up to a constant factor. Cames van Batenburg, Kang and Pirot state it as their Theorem 4 ([[../library/extremal_graph_theory/camesvanbatenburg_2020_strong_cliques_forbidden_cycles/_index|source card]]): $\chi'_2(G)\le(2+\varepsilon)\Delta^2/\log\Delta$ for $C_4$-free graphs and large $\Delta$, "sharp up to the multiplicative constant factor". The site labels the problem OPEN, so the curator's commentary crediting the thesis is not listed as review.