Problem 149

The strong chromatic index of a graph $G$ , denoted by $\mathrm{sq}(G)$ , is the minimum $k$ such that the edges of $G$ can be partitioned into $k$ sets of 'strongly independent' edges, that is, such that the subgraph of $G$ induced by each set is the union of vertex-disjoint edges.

Is it true that, for any graph $G$ with maximum degree $\Delta$ ,

\mathrm{sq}(G)\leq\frac{5}{4}\Delta^2?

Source: erdosproblems.com/149

Graph theory

Wiki page

Status

Open

No claim settles this problem.

Open. No proof, disproof or proof claim for the statement was found in the search whose scope the Current assessment records. The best refereed upper bound is $\mathrm{sq}(G)\le1.772\Delta^2$ for every graph with $\Delta$ at least some $\Delta_0$ (Hurley, de Joannis de Verclos and Kang, Theorem 1.6, Advances in Combinatorics 2022), after Molloy and Reed's $1.998\Delta^2$ , Bruhn and Joos's $1.93\Delta^2$ and Bonamy, Perrett and Postle's $1.835\Delta^2$ , all for large $\Delta$ ; a preprint of July 2026 (Davey, Hurley, de Joannis de Verclos, Kang and Volec, Theorem 1.1) claims $1.73\Delta^2$ for large $\Delta$ , unrefereed. The statement is proved for $\Delta\le3$ ( $\mathrm{sq}(G)\le10$ , Horák, He and Trotter 1993 and, independently, Andersen 1992; see their claim pages (Andersen, 1992)), for $C_4$ -free graphs of large $\Delta$ by Mahdian's bound $(2+o(1))\Delta^2/\log\Delta$ (claim page (Mahdian, 2000)), for graphs of large $\Delta$ without a fixed bipartite subgraph $H$ by Vu's extension of that bound (claim page (Vu, 2002)), and for $\Delta=4$ the site records $21$ against the conjectured $20$ (Huang, Santana and Yu 2018). The clique form stands at $\omega(L(G)^2)\le\frac43\Delta^2$ (Faron and Postle, refereed), with a 2026 preprint at $\frac{2607}{1987}\Delta^2$ , and reaches $\frac54\Delta^2$ for triangle-free graphs. This is a bounded negative finding, not a certificate of openness.

Er88: Erdős, P., Problems and results in combinatorial analysis and graph theory. Discrete Math. 72 (1988), 81--92; Section 1, printed p. 81. Library home: Erdős 1988.
FGST89: Faudree, R. J., Gyárfás, A., Schelp, R. H. and Tuza, Zs., Induced matchings in bipartite graphs. Discrete Math. 78 (1989), no. 1--2, 83--87, doi:10.1016/0012-365X(89)90163-5 (received 2 December 1987); printed pp. 83--84. Library home: Faudree 1989; paged at Faudree 1989, Problems (p. 83) and Faudree 1989, Theorem 1 (p. 84).
CGTT90: Chung, F. R. K., Gyárfás, A., Tuza, Z. and Trotter, W. T., The maximum number of edges in $2K_2$ -free graphs of bounded degree. Discrete Math. 81 (1990), no. 2, 129--135, doi:10.1016/0012-365X(90)90144-7 (the site's text prints no volume). Theorem 4, p. 131. Library home: Chung 1990 (the author's copy from W. T. Trotter's publication page); paged at Chung 1990, Theorem 4 (p. 131).
HHT93: Horák, P., He, Q. and Trotter, W. T., Induced matchings in cubic graphs. J. Graph Theory 17 (1993), no. 2, 151--160, doi:10.1002/jgt.3190170204. The Theorem, p. 152. Library home: Horák and Trotter 1993 (the author's copy from Trotter's publication page, the address the site's thread links); paged at Horák and Trotter 1993, Theorem (p. 152).
92: The site's key carries no reference text. The thread (30 November 2025) and the Crossref record identify the paper as Andersen, L. D., The strong chromatic index of a cubic graph is at most 10. Discrete Math. 108 (1992), no. 1--3, 231--252, doi:10.1016/0012-365X(92)90678-9 (received 4 January 1991), and the printed paper confirms the citation (its p. 231). Theorem 1, printed p. 250 (PDF p. 20 of the publisher's open-archive file); the definitions and the graph $G_{10}$ , pp. 231--232 (PDF pp. 1--2). Library home: Andersen 1992; paged at Andersen 1992, Theorem 1.
MoRe97: Molloy, M. and Reed, B., A bound on the strong chromatic index of a graph. J. Combin. Theory Ser. B 69 (1997), no. 2, 103--109, doi:10.1006/jctb.1997.1724 (received 10 October 1995). Theorem 1, printed p. 104 (PDF p. 2 of the version of record in the publisher's open archive); the definitions and the Erdős--Nešetřil question, p. 103 (PDF p. 1); Lemmas 1 and 2, p. 105 (PDF p. 3); the Remarks, p. 108 (PDF p. 6). Library home: Molloy and Reed 1997; paged at Molloy and Reed 1997, Theorem 1.
BrJo18: Bruhn, H. and Joos, F., A stronger bound for the strong chromatic index. Combin. Probab. Comput. 27 (2018), no. 1, 21--43, doi:10.1017/S0963548317000244 (published online 19 July 2017; an extended abstract in Electron. Notes Discrete Math. 49 (2015), 277--284). Cited from arXiv:1504.02583v1 (10 April 2015, 22 pp.); Theorem 1, p. 1; Theorem 3 and Conjecture 2, p. 2. Library home: Bruhn and Joos 2018; paged at Bruhn and Joos 2018, Theorem 1 (p. 1) and Bruhn and Joos 2018, Theorem 3 (p. 2).
BPP22: Bonamy, M., Perrett, T. and Postle, L., Colouring graphs with sparse neighbourhoods: bounds and applications. J. Combin. Theory Ser. B 155 (2022), 278--317, doi:10.1016/j.jctb.2022.01.009. Cited from arXiv:1810.06704v1 (15 October 2018, 27 pp.); Theorem 1.11, p. 4. Library home: Bonamy 2022; paged at Bonamy 2022, Theorem 1.11 (p. 4).
HJK22: Hurley, E., de Joannis de Verclos, R. and Kang, R. J., An improved procedure for colouring graphs of bounded local density. Adv. Comb. 2022:7, 33 pp., doi:10.19086/aic.2022.7 (received 13 October 2020, published 22 September 2022); cited from the published text (also arXiv:2007.07874v3). Conjecture 1.4, Theorem 1.5 and Theorem 1.6, p. 4. Library home: Hurley 2022; paged at Hurley 2022, Theorem 1.6 (p. 4) and Hurley 2022, Conjecture 1.4 (p. 4).
Sl16: Śleszyńska-Nowak, M., Clique number of the square of a line graph. Discrete Math. 339 (2016), no. 5, 1551--1556, doi:10.1016/j.disc.2016.01.003. Cited from arXiv:1504.06585v2 (30 April 2015, 9 pp.); Theorem 5, pp. 2 and 5. Library home: Sleszynskanowak 2016; paged at Sleszynskanowak 2016, Theorem 5 (pp. 2 and 5).
FaPo19: Faron, M. and Postle, L., On the clique number of the square of a line graph and its relation to maximum degree of the line graph. J. Graph Theory 92 (2019), no. 3, 261--274, doi:10.1002/jgt.22452 (published online 30 January 2019). Cited from arXiv:1708.02264v1 (7 August 2017, 11 pp.), whose title ends "and its relation to Ore-degree"; Conjectures 1.1--1.2 and Theorems 1.3--1.4, pp. 1--2; Corollary 1.10, p. 3; Corollary 1.11, p. 4. Library home: Faron and Postle 2019; paged at Faron and Postle 2019, Corollary 1.11 (p. 4) and Faron and Postle 2019, Corollary 1.10 (p. 3).
CKP20: Cames van Batenburg, W., Kang, R. J. and Pirot, F., Strong cliques and forbidden cycles. Indag. Math. (N.S.) 31 (2020), no. 1, 64--82, doi:10.1016/j.indag.2019.09.003. Cited from arXiv:1903.06087v1 (14 March 2019, 24 pp.); Conjecture 1, p. 1; Conjectures 2--3 and Theorems 4--6, p. 2; Theorem 8, p. 3; the remark on the general clique bound, p. 4. Library home: Camesvanbatenburg 2020; paged at Camesvanbatenburg 2020, Theorem 6 (p. 2).
HSY18: Huang, M., Santana, M. and Yu, G., Strong chromatic index of graphs with maximum degree four. Electron. J. Combin. 25 (2018), no. 3, Paper 3.31, doi:10.37236/7016 (published 24 August 2018). Cited from the journal's open-access PDF; Conjecture 1 and Theorem 2, p. 2. Library home: Huang 2018; paged at Huang 2018, Theorem 2 (p. 2).
Da26: Davey, E., Hurley, E., de Joannis de Verclos, R., Kang, R. J. and Volec, J., Strong edge-colouring via local flag algebras. arXiv:2607.17421v1 (19 July 2026), 23 pp.; a preprint with no journal record on its arXiv listing. Theorems 1.1--1.4 and the "Note on AI and Lean", pp. 1--2; the "AI usage declaration", p. 22. Library home: Davey 2026; paged at Davey 2026, Theorem 1.1 (p. 1).
KMP26: Kumar, H., Mohar, B. and Pragada, S., An improved bound for the strong clique index of graphs. arXiv:2607.02698v1 (2 July 2026), 15 pp.; a preprint; Corollary 1.7, p. 3; the "AI statement", p. 13. Library home: Kumar and Pragada 2026; paged at Kumar and Pragada 2026, Corollary 1.7 (p. 3).
HYY26: Hao, Y., Yang, T. and Yu, X., Strong chromatic index of bipartite graphs. arXiv:2606.23824v2 (23 July 2026), 12 pp.; a preprint; the abstract and Theorem 1.2, p. 2. Library home: Hao 2026; paged at Hao 2026, Theorem 1.2 (p. 2).
BBDX26: Bi, R., Bradshaw, P., Dhawan, A. and Xu, J., The strong chromatic index of $K_{t,t}$ -free graphs. arXiv:2603.15207v1 (16 March 2026); cited from the abstract on its arXiv record only.
Ma00: Mahdian, M., The strong chromatic index of graphs. M.Sc. thesis, University of Toronto (2000), handle 1807/14823 (the University of Toronto repository copy the site's thread links); published as Mahdian, M., The strong chromatic index of $C_4$ -free graphs. Random Structures Algorithms 17 (2000), no. 3--4, 357--375. Neither is held; the $C_4$ -free theorem is quoted through [CKP20], Theorem 4, and recorded as an accepted partial claim, refereed, on its claim page (Mahdian, 2000).
Vu02: Vu, V. H., A general upper bound on the list chromatic number of locally sparse graphs. Combin. Probab. Comput. 11 (2002), no. 1, 103--111, doi:10.1017/S0963548301004898. Not held; recorded as a claimed partial claim on its claim page (Vu, 2002).
BBPP83: Bermond, J.-C., Bond, J., Paoli, M. and Peyrat, C., Graphs and interconnection networks: diameter and vulnerability. Surveys in Combinatorics 1983, London Math. Soc. Lecture Note Ser. 82 (1983), 1--30; the passage on graphs of line diameter 2 (PDF p. 13 of the HAL deposit hal-02447135, left- and right-hand typescript pages). Not a site key for this problem. Library home: Bermond 1983; paged at Bermond 1983, Section 6, the case Δ = 2 (PDF p. 13 of the deposit).

Problem 149

Status

Proof claims

Discussion