{"id":"e8b438b6-97e9-4ab4-bcce-7c56fc7a45d2","arxiv_id":"2608.22537","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every B-free graph G satisfies α(G)+ω(G) ≥ |V(G)| - 1, resolving the B-Free Graphs Conjecture of Litjens, Polak and Sivaraman.","lead":"This paper proves a 2019 conjecture about B-free graphs: such graphs must satisfy alpha plus omega at least n minus one. The proof combines Hall-type matching lemmas with a computer check of twenty-one small feasibility systems.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The structural reduction is sound, but Theorem 1.1 rests on the unverified 21-case infeasibility claim (Prop. 4.1); the symmetry-breaking constraints' soundness is asserted without proof.","rationale":"The reader's verdict (CONDITIONAL) identifies the computational infeasibility of the 21 systems as the weakest assumption; my review converges on the same point. I checked the reductions: the Hall-exchange argument (Lemma 2.1), the two-vertex difference bound (Cor. 2.2), the corona matching (Prop. 2.3), and the double-counting bounds in Lemmas 3.1–3.2 are all consistent; Table 1 is complete up to complementation. The only load-bearing step not established by the text is Proposition 4.1. The two verifiers mitigate risk but are not formal certificates, and the symmetry-breaking ordering constraints add an unverified soundness condition. A certified independent UNSAT proof would fully resolve the concern; until then the conditional verdict is appropriate. No change to the reader's verdict is needed.","tokens_in":6127,"tokens_out":22042,"duration_ms":203139,"concrete_test":"Write a fresh constraint generator from the displayed equations (4.1)–(4.10), omitting the symmetry-breaking order constraints, and solve all 21 tuples with a third-party exact SAT solver (e.g., CaDiCaL) in proof-producing mode; validate every emitted UNSAT proof with a formally verified checker such as dpr-trim. Reproducing UNSAT on the unrestricted systems settles both the infeasibility claim and the symmetry-breaking soundness question.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I found no internal gap in the exchange and counting arguments of Sections 2 and 3; the bounds in Lemmas 3.1–3.2 and Table 1 follow from the stated hypotheses. The theorem therefore depends entirely on Proposition 4.1, which is not proved in the text but outsourced to two supplied programs. The two programs are called independent but are generated from the same Section 4 specification, so a shared misunderstanding of (4.5)–(4.7) or of the low-degree selector encoding would make both fail identically. The --check-encoding routine validates only the forbidden-family inequalities (4.3)–(4.4), not the alpha/omega, matching, or symmetry-breaking parts. In particular, the assertion that the added ordering constraints on y- and z-selectors are satisfiable after relabeling by every feasible solution is unproven; if wrong, a solver could return UNSAT for a satisfiable system. The HiGHS/SciPy MILP path is floating-point and supplies no certificate. Until an independent run or a machine-checked UNSAT certificate confirms all 21 infeasibilities, Theorem 1.1 is conditional.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims a proof of the B-Free Graphs Conjecture of Litjens, Polak and Sivaraman, asserting that every graph excluding the six-vertex bipartite graphs with a perfect matching and their complements satisfies α(G)+ω(G) ≥ |V(G)|−1. The proof proceeds by taking a smallest counterexample, using Hall-type exchange arguments (Lemma 2.1 and Corollary 2.2) to show that maximum stable sets (and dually maximum cliques) differ in at most two vertices, then applying a core-corona matching lemma to obtain |α(G)−ω(G)| ≤ 2. Double counting in Sections 3 leads to twenty-one finite parameter cases listed in Table 1. Section 4 encodes each case as a binary feasibility system and asserts, via two supplied computer programs, that all twenty-one systems are infeasible. Theorem 1.1 then follows from the structural reduction plus this computational exclusion.","tokens_in":6372,"tokens_out":16533,"duration_ms":144934,"significance":"If the computational step is valid, this settles a conjecture from 2019 and gives a clean structural proof that the forbidden family B forces the sum-perfect inequality up to an additive deficit of one. The exchange and counting arguments in Sections 2 and 3 are elegant and appear internally sound, and the exhaustive validation of the forbidden-family encoding on all 32768 labelled six-vertex graphs is a commendable safeguard. The central weakness is that the theorem rests entirely on Proposition 4.1, whose twenty-one infeasibility claims are delegated to unverified computer programs; no machine-checkable certificates are provided. Because the structural reduction is genuinely novel and reduces the problem to a finite check, the paper has the potential to be a significant contribution once the computational verification is made robust and independently auditable.","major_comments":[{"comment":"The proof of Theorem 1.1 depends entirely on the twenty-one infeasibility assertions of Proposition 4.1, but these are verified only by the two supplied programs verify.py and verify_sat.cpp. Both programs are generated from the same mathematical specification in Section 4, so a shared misunderstanding of constraints (4.5)–(4.10) would make both fail identically. The --check-encoding routine validates only the forbidden-family inequalities (4.3)–(4.4); it does not check the α/ω constraints (4.1)–(4.2), the matching constraints (4.6)–(4.10), or the symmetry-breaking ordering. The HiGHS/SciPy MILP path is floating-point and returns no certificate, and the self-contained SAT solver is not formally verified. To make the proof auditable, the author should provide machine-checked UNSAT certificates (e.g., DRAT) for all twenty-one systems, or an independent implementation from a separate specification, before the theorem can be regarded as established.","section":"Section 4, Proposition 4.1"},{"comment":"The symmetry-breaking constraints added in verify.py are asserted to be sound with the sentence 'every feasible labelled solution has a relabeling satisfying them,' but no proof of this assertion is given, and the exact ordering constraints are not specified in the text. In particular, the phrase 'on two exceptional labels' is ambiguous, and for the t=1 cases there are three vertices outside S∪K. If these ordering constraints happen to exclude some feasible solution rather than merely break symmetry, the solver could return UNSAT for a satisfiable system, invalidating Proposition 4.1. The author should either provide a rigorous proof of the soundness of the symmetry-breaking constraints or remove them and rerun the verification without them.","section":"Proof of Proposition 4.1, Section 4"},{"comment":"The paper states that 'This description is also a direct soundness proof for the supplementary verifier,' but the description only explains what constraints are generated; it does not prove that the programs correctly implement those constraints or that the solver results are trustworthy. The two programs are described as independent, yet both derive from the same mathematical specification, so the independence does not protect against a shared modeling error. The paper should state explicitly that the proof is computer-assisted, describe the exact solver versions and commands, and make the full run logs and any certificates available, so that a third party can reproduce the infeasibility verdicts.","section":"Section 4, general verification methodology"}],"minor_comments":[{"comment":"The command './verify sat --all --time-limit 600' appears to have a typo; the program name in the text is verify_sat.cpp, so the command should likely be './verify_sat --all --time-limit 600'.","section":"Section 4, paragraph after (4.10)"},{"comment":"The exact symmetry-breaking ordering constraints on the y- and z-selectors should be written out in the text (or in an appendix), including how the 'exceptional labels' are chosen, so that the reader can check the soundness claim.","section":"Proof of Proposition 4.1, Section 4"},{"comment":"The sentence 'At order six the only remaining numerical possibility is a=w=2' is correct after assuming a≥w and noting that α=1 or ω=1 would force a complete or edgeless graph, but this reasoning could be spelled out more explicitly for clarity.","section":"End of Section 3"},{"comment":"Using 'a y_v' and 'w z_v' as products is standard, but writing 'a·y_v' and 'w·z_v' might prevent any ambiguity with subscripts.","section":"Section 4, equations (4.5) and (4.8)"},{"comment":"The phrase 'two disjoint stable triples with three independent cross-edges' and its complement are good informal descriptions, but the formal definition of B in the introduction would be clearer if it specified that the six-vertex graph is induced and not merely a subgraph.","section":"Abstract and Section 1"}],"recommendation":"major_revision","confidential_remarks":"The structural part of the proof is strong and the conjecture is significant, so the paper deserves a chance. The sole obstacle is the computational verification of Proposition 4.1: the current evidence is not sufficient for a mathematical proof because no certificates or independent verification are supplied. If the author provides machine-checked UNSAT certificates or a fully independent confirmation of all twenty-one infeasibilities, I would support acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Frijio's paper is the first genuine attack on the B-Free Graphs Conjecture, and it gets further than I expected. The minimal-counterexample machinery in Sections 2 and 3 is the real contribution: the Hall-type exchange lemma and the core-corona matching argument are new and they do force |a-w|≤2 and then reduce a counterexample to 21 parameter tuples. I read those sections carefully and found no internal gap. The double-counting bounds in Lemmas 3.1–3.2 follow from the stated hypotheses. The encoding of B-freeness is also checked brutally: the verifier compares the inequality encoding against the definition on all 32768 labelled six-vertex graphs, and they agree. That is real evidence.\n\nThe soft spot is exactly where the reader put it. Theorem 1.1's proof ends at Proposition 4.1, which states that 21 explicit 0–1 systems are infeasible. The paper does not prove that in text; it supplies two programs, verify.py and verify_sat.cpp. I could not execute them from the arXiv package, and the stress-test note identifies a specific gap: the symmetry-breaking constraints on y- and z-selectors are asserted to be satisfiable after relabeling by every feasible solution, but no proof is given. If that assertion is wrong, a solver could return UNSAT for a satisfiable system. Also, the HiGHS/SciPy path is floating-point with no certificate; the SAT path is exact but generated from the same Section 4 specification, so a shared encoding error would make both fail identically.\n\nThat said, I do not see this as a flaw in the structural mathematics. The computational claim is checkable; it just has not been independently checked. The honest status is 'conditional on Proposition 4.1'.\n\nWho this is for: anyone working on sum-perfect graphs, hereditary graph inequalities, or Nordhaus-Gaddum-type problems. The paper deserves a serious referee—send it to review—but I would not cite it as a proved theorem until Prop 4.1 has an independent run or formal UNSAT certificates. Minor editorial: the definition of B is displayed twice in Section 1; the duplicate should go.","headline":"A credible structural proof of the B-Free Graphs Conjecture whose final step rests on 21 unverified computational infeasibility claims; worth refereeing but not yet a settled theorem.","tokens_in":6801,"tokens_out":1604,"would_cite":false,"duration_ms":15197,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"pith_extraction":{"msc":["05C17","05C35","05C69"],"pacs":[],"model":"deepseek-v4-flash","headline":"B-free graphs come within one vertex of the sum-perfect bound","keywords":["B-free graphs","sum-perfect graphs","stability number","clique number","forbidden induced subgraph","Hall-type exchange","binary feasibility system","computational verification"],"falsifier":"Run the supplied verifiers (verify.py --all and verify_sat.cpp --all); if any of the twenty-one systems returns feasible or SAT instead of infeasible/UNSAT, the proof collapses. Alternatively, construct a $\\mathcal{B}$-free graph with any parameter tuple in Table 1 satisfying $\\alpha+\\omega = n-2$.","tokens_in":5928,"feed_emoji":"🕸️","tokens_out":9739,"duration_ms":74687,"temperature":0.7,"pith_summary":"This paper proves the B-Free Graphs Conjecture: if a graph contains no induced six-vertex bipartite graph with a perfect matching, and no complement of such a graph, then its stability number plus its clique number is at least the number of vertices minus one. A smallest hypothetical counterexample is shown through Hall-type exchange and core-corona matching arguments to have at most fourteen vertices and $|\\alpha(G)-\\omega(G)|\\le 2$. The remaining twenty-one parameter cases are encoded as binary feasibility systems, and their infeasibility is checked by two independent exact solvers. If the proof holds, the conjecture from [16] is settled and the hereditary deficit-one bound for $\\alpha+\\omega$ is fully characterized by one forbidden family $\\mathcal{B}$.","feed_headline":"B-free graphs come within one vertex of the sum-perfect bound","feed_subtitle":"The 2019 conjecture is now a theorem: for B-free graphs, α+ω ≥ n−1.","key_machinery":"The core-corona matching lemma, a specialization of the set-and-collection lemma [15], is the mechanism that carries the argument: for every maximum stable set $S$ in a smallest counterexample, there are at least $a$ distinct vertices outside $S$ with at most two neighbours in $S$, and they can be matched to $S$ by edges; the dual statement holds for maximum cliques via complementation. This yields the bounds $2a\\le n$, $2w\\le n$, hence $|a-w|\\le 2$, and feeds a double-counting inequality (such as (3.2) and (3.4)) that caps the order at fourteen. The final step is the binary feasibility system (4.1)--(4.10), whose twenty-one instances on at most fourteen vertices are each verified infeasible by two independent exact encodings.","core_discovery":"The central claim, Theorem 1.1, is that every $\\mathcal{B}$-free graph $G$ satisfies $\\alpha(G)+\\omega(G)\\ge |V(G)|-1$, where $\\mathcal{B}$ consists of the six-vertex bipartite graphs with a perfect matching and their complements. The proof takes a smallest counterexample and derives from Corollary 2.2 that two maximum stable sets differ in at most two vertices and that the same holds dually for maximum cliques. Proposition 2.3, via the set-and-collection lemma, provides a matching from any maximum stable set into low-degree vertices outside it, which forces $2a\\le n$ and $2w\\le n$ and consequently $|a-w|\\le 2$. Double counting on the edges between dense and sparse parts then bounds the order by fourteen, leaving twenty-one tuples $(n,a,w,t)$; for each tuple the system (4.1)--(4.10) is infeasible (Proposition 4.1), ruling out every residual possibility.","pith_inferences":["This exchange-and-matching strategy could plausibly extend to other hereditary bounds of the form $\\alpha+\\omega \\ge n - d$ for larger forbidden families, with the same reduction to finite feasibility systems.","The twenty-one infeasible systems may admit a common human-readable certificate (for instance, a small set of covering inequalities); discovering one would remove the dependence on computer verification.","The paper does not exhibit extremal $\\mathcal{B}$-free graphs achieving equality $\\alpha+\\omega = n-1$; constructing infinite families of such graphs would show the bound is tight and illuminate the extremal structure.","A formal proof assistant could certify the SAT/MILP results of Proposition 4.1, making the computational part fully machine-checked."],"forward_implications":["The B-Free Graphs Conjecture is confirmed: no $\\mathcal{B}$-free graph can have $\\alpha(G)+\\omega(G)<|V(G)|-1$.","Because $\\mathcal{B}$-freeness is hereditary, every induced subgraph of a $\\mathcal{B}$-free graph also satisfies the same inequality.","The proof reduces a potential infinite search to exactly twenty-one finite binary systems, each on at most fourteen vertices, so the theorem's correctness can be rechecked by running the two supplied exact verifiers.","The methods indicate that a smallest counterexample to the inequality, if any existed, would have at least fifteen vertices, since all smaller candidates are excluded."],"supporting_citations":[{"why":"defines sum-perfect graphs, introduces the class B, and states Conjecture 3.1 proved here.","marker":"[16]"},{"why":"provides Hall's condition used in Lemma 2.1's matching argument.","marker":"[9]"},{"why":"the set-and-collection lemma specialized in Proposition 2.3 to get low-degree targets matchable into a maximum stable set.","marker":"[15]"},{"why":"the mixed-integer optimizer used by verify.py to certify infeasibility of the systems.","marker":"[13]"},{"why":"the Python interface used to construct and solve the binary systems within verify.py.","marker":"[20]"}],"fun_headline_variants":["B-free graphs conjecture proven","B-free graphs satisfy α+ω ≥ n−1","2019 B-free graphs conjecture settled","B-free graphs within one of sum-perfect","Proof of B-free graphs conjecture"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The theorem stands on Proposition 4.1, the infeasibility of the twenty-one binary systems (4.1)--(4.10), which is established only by the two supplied computer programs; if either encoding or solver run is wrong, the proof fails.","fun_headline_variants_meta":{"raw":{"variants":["B-free graphs conjecture proven","B-free graphs satisfy α+ω ≥ n−1","2019 B-free graphs conjecture settled","B-free graphs within one of sum-perfect","Proof of B-free graphs conjecture"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000828,"raw_usage":{"total_tokens":3600,"prompt_tokens":912,"completion_tokens":2688,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":528,"completion_tokens_details":{"reasoning_tokens":2624}},"tokens_in":528,"tokens_out":2688,"duration_ms":20188,"temperature":1.0,"reasoning_tokens":2624,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-27T18:27:51.448477+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the supplied verifiers (verify.py --all and verify_sat.cpp --all); if any of the twenty-one systems returns feasible or SAT instead of infeasible/UNSAT, the proof collapses. Alternatively, construct a $\\mathcal{B}$-free graph with any parameter tuple in Table 1 satisfying $\\alpha+\\omega = n-2$.","supporting_citations":[{"cited_title":"Polak, and Vaidy Sivaraman","cited_arxiv_id":null,"evidence_quote":"defines sum-perfect graphs, introduces the class B, and states Conjecture 3.1 proved here."},{"cited_title":"Levit and Eugen Mandrescu","cited_arxiv_id":null,"evidence_quote":"the set-and-collection lemma specialized in Proposition 2.3 to get low-degree targets matchable into a maximum stable set."}],"review_version":1}