Cardoso–Luz conjecture on adverse graphs
An adverse graph is a graph without isolated vertices such that and are integers, and, for every vertex ,
Here is the optimal value of the quadratic stability-number bound and is the least eigenvalue of . A graph is a -graph when it belongs to the class defined in the paper.
Cardoso–Luz conjecture. All adverse graphs are -graphs.
Computational tests with adverse graphs supported the conjecture, but it remains open. Its resolution would clarify the polynomial-time recognition of -graphs.
References
- Domingos M. Cardoso, “A survey on graphs with convex quadratic stability number”, arXiv:1811.05516 (2018).
Progress summary
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 -graph. The 2018 survey records this as Conjecture and says computational tests supported it while it remained open.
Known results
- For adverse graphs, recognizing a -graph is equivalent to finding a -regular set, where .
- This case is identified as the main obstacle to a general polynomial-time recognition algorithm for -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 is adverse, with and , but is not a -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 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.