← All problems

Maximum sigma_t-irregularity conjecture for connected triangle-free graphs

2 years old · traced to

Let GG be a connected triangle-free graph on nn vertices. Write σt(G)\sigma_t(G) for its σt\sigma_t-irregularity. Among such graphs, the extremal complete bipartite graphs are conjectured to have maximum σt(G)\sigma_t(G).

Triangle-free extremal conjecture. Among connected triangle-free graphs on nn vertices, the extremal complete bipartite graphs have the maximum σt(G)\sigma_t(G)-irregularity.

The paper proves the corresponding extremal result among complete bipartite graphs and proposes this conjecture as the extension to all connected triangle-free graphs; its status is not resolved in the supplied text.

References
  1. Slobodan Filipovski, Darko Dimitrov, Martin Knor and Riste Škrekovski, “Some results on σ_t-irregularity”, arXiv:2411.04881 (2024).

Progress summary

Refreshed
Open · progress reported

The conjecture remains open: the published paper settles only complete bipartite graphs, while an unverified proof claim has appeared.

The conjecture says that, among connected triangle-free graphs on nn vertices, an extremal complete bipartite graph maximizes σt(G)\sigma_t(G). The published source explicitly presents this extension as open.

Known results

  • For connected triangle-free GG, σt(G)≤m(n2−4m)\sigma_t(G)\le m(n^2-4m), with equality exactly for complete bipartite graphs.
  • Among complete bipartite graphs, maximizers have part sizes near n4(2−2)\frac n4(2-\sqrt2) and n4(2+2)\frac n4(2+\sqrt2) for n≥7n\ge 7.
  • Computations find stars maximal for 2≤n≤92\le n\le 9, both K1,9K_{1,9} and K2,8K_{2,8} maximal for n=10n=10, and K2,9K_{2,9} maximal for n=11n=11.

November 7, 2026 community submission

A submitted proof argues that every maximizer is complete bipartite and claims to prove the conjecture in full. This claim is unverified and does not establish a solved status.

Current status (as of November 2026): The complete-bipartite case and the stated upper bound are settled, but the full connected triangle-free conjecture remains open because the new proof claim is unverified.

Sources

Solutions 1

Complete bipartite graphs maximise sigma_t-irregularity among connected triangle-free graphsSee full solutionHide full solution

Result and scope. For every n>=2 and every maximiser a of a(n-a)(n-2a)^2 over 1<=a<n, K_{a,n-a} is connected, triangle-free and has sigma_t at least that of every connected triangle-free graph on n vertices; every attainer is complete bipartite with nonempty parts. Proves arXiv:2411.04881v1 Conjecture 24 / Ars Math. Contemp. 26 (2026) Conjecture 6.1 in full.

Complete proof: Complete bipartite graphs maximise sigma_t-irregularity among connected triangle-free graphs · PDF.

The paper page contains the supplementary proof-source JSON and extract_sources.py. The linked paper supplies the complete argument and states the precise scope of the Lean certificate, ordinary proofs, supporting computations, and source interpretation. Those qualifications are retained here; a supporting computation is not a proof of a broader statement.

This is an AI-assisted research preprint. Internal review is not external journal peer review. Bounded prior-art searches do not establish worldwide priority. See the paper for formalization and trust limits.