← All problems

Cardoso–Luz conjecture on adverse graphs

8 years old · traced to

An adverse graph is a graph HH without isolated vertices such that υ(H)\upsilon(H) and λmin⁡(H)\lambda_{\min}(H) are integers, and, for every vertex i∈V(H)i\in V(H),

υ(H−NH(i))=υ(H),λmin⁡(H−NH(i))=λmin⁡(H).\upsilon(H-N_H(i))=\upsilon(H),\qquad \lambda_{\min}(H-N_H(i))=\lambda_{\min}(H).

Here υ(H)\upsilon(H) is the optimal value of the quadratic stability-number bound and λmin⁡(H)\lambda_{\min}(H) is the least eigenvalue of HH. A graph is a Q\mathcal{Q}-graph when it belongs to the class Q\mathcal{Q} defined in the paper.

Cardoso–Luz conjecture. All adverse graphs are Q\mathcal{Q}-graphs.

Computational tests with adverse graphs supported the conjecture, but it remains open. Its resolution would clarify the polynomial-time recognition of Q\mathcal{Q}-graphs.

References
  1. Domingos M. Cardoso, “A survey on graphs with convex quadratic stability number”, arXiv:1811.05516 (2018).

Progress summary

Refreshed
Open

A submitted preprint claims a counterexample, but the conjecture remains unverified and therefore open.

The Cardoso–Luz conjecture asks whether every adverse graph is a Q\mathcal{Q}-graph. The 2018 survey records this as Conjecture 4.24.2 and says computational tests supported it while it remained open.

Known results

  • For adverse graphs, recognizing a Q\mathcal{Q}-graph is equivalent to finding a (0,τ)(0,\tau)-regular set, where τ=−λmin⁡(G)\tau=-\lambda_{\min}(G).
  • This case is identified as the main obstacle to a general polynomial-time recognition algorithm for Q\mathcal{Q}-graphs.
  • Reported computational tests supported the conjecture.

Community submission (unverified)

Posted November 7, 2026: a submitted proof argues that the cyclic Latin-square graph of order 66 is adverse, with λmin⁡=−3\lambda_{\min}=-3 and υ=6\upsilon=6, but is not a Q\mathcal{Q}-graph. If correct, this would refute the conjecture; the proof and claimed counterexample have not been independently verified.

Current status (as of November 2026): The conjecture remains open; the submitted November 7, 2026 counterexample is unverified.

Sources

Solutions 1

An adverse non-Q graph from the cyclic Latin square of order sixSee full solutionHide full solution

Result and scope. The cyclic Latin square graph of order 6 (cells of Z6xZ6 adjacent when sharing a row, column or symbol) has lambda_min = -3 and upsilon = 6, both unchanged after deleting every open neighbourhood, and no isolated vertices, so it is adverse; its stability number is 5 by the transversal parity obstruction, so it is not a Q-graph. This refutes Cardoso-Luz Conjecture 4.2 (survey arXiv:1811.05516, Optimization 69(1) 2020) that all adverse graphs are Q-graphs, also under the JCO 2016 'non complete' reading.

Complete proof: An adverse non-Q graph from the cyclic Latin square of order six · 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.