A Proof of the B-Free Graphs Conjecture

Domenico Frijio

REVIEW 3 major objections 5 minor 21 references

A Proof of the B-Free Graphs Conjecture

T0 review · 3 major / 5 minor · reviewed 2026-08-27 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read B-free graphs come within one vertex of the sum-perfect bound

desk verdict 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. read the letter →

arxiv 2608.22537 v1 pith:TBC5CLCU submitted 2026-08-23 math.CO

Domenico Frijio This is my paper · ORCID

classification math.CO MSC 05C1705C3505C69

keywords B-freegraphssum-perfectstabilitynumbercliqueforbiddeninducedsubgraphHall-typeexchangebinaryfeasibilitysystemcomputationalverification

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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}$.

What carries the argument

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.

What would settle it

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$.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

That 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'.

Who 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.

Referee Report

3 major / 5 minor

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.

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 (3)

[Section 4, Proposition 4.1] 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.
[Proof of Proposition 4.1, Section 4] 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 4, general verification methodology] 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.

minor comments (5)

[Section 4, paragraph after (4.10)] 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'.
[Proof of Proposition 4.1, Section 4] 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.
[End of Section 3] 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 4, equations (4.5) and (4.8)] 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.
[Abstract and Section 1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the proof is a minimal-counterexample reduction to a finite infeasibility check, with no fitted parameters and no load-bearing self-citation.

full rationale

The derivation chain is self-contained. Theorem 1.1 is proved by assuming a smallest counterexample with alpha+omega=n-2 as in equation (2.1); Lemma 2.1 and Corollary 2.2 are Hall-type exchange arguments whose only external input is the elementary matching lemma [15], which is not by the current author and does not assume the target result. Proposition 2.3 uses only Corollary 2.2 and the external set-and-collection lemma. Lemmas 3.1 and 3.2 derive explicit numerical bounds from double counting, and Table 1 lists the resulting 21 parameter cases. The remaining work is Proposition 4.1, which is not a fitted prediction: constraints (4.1)-(4.10) encode the definitions of alpha, omega, B-freeness and the matching guarantees, and the infeasibility is checked by two independently written exact encodings. No parameter is trained on the target inequality, no alternative is ruled out by a uniqueness theorem from the authors, and no known result is merely renamed. Even though the computational verification is load-bearing and could be wrong, that is a soundness or reproducibility concern, not circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters or invented entities. The proof relies on standard matching and Ramsey facts, an external lemma of Levit and Mandrescu, and the correctness of the computational verifiers that decide the twenty-one finite systems.

assumptions (4)

standard math Hall's marriage theorem: a matching from A minus B to B minus A exists if the Hall condition holds.
Used in Lemma 2.1 to prove the exchange matching between two maximum stable sets.
standard math R(3,3)=6: every graph on six vertices contains a triangle or an independent set of size three.
Used in Section 3 to exclude n=6 with a=w=2.
standard math Levit-Mandrescu set-and-collection lemma [15]: for a maximum stable set S, there is a matching from S minus core_alpha(G) into corona_alpha(G) minus S.
External published lemma, cited but not proved; Proposition 2.3 depends on it.
ad hoc to paper The two verifiers correctly encode constraints (4.1)-(4.10) and correctly report infeasibility and UNSAT for all twenty-one cases.
Proposition 4.1 rests entirely on these computational results; the text provides commands and claims source digests but no human-readable certificate.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Proof of the B-Free Graphs Conjecture." pith.science (2026). https://pith.science/paper/TBC5CLCU

@misc{pith2026260822537,
  author       = {Pith},
  title        = {Pith review of: A Proof of the B-Free Graphs Conjecture},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TBC5CLCU}},
  note         = {Machine review of arXiv:2608.22537}
}

abstract

Let $\mathcal{B}$ be the class consisting of the six-vertex bipartite graphs that possess a perfect matching and their complements. It is proved that every $\mathcal{B}$-free graph $G$ satisfies $\alpha(G)+\omega(G)\ge |V(G)|-1$. This establishes Conjecture 3.1 of Litjens, Polak and Sivaraman (B-Free Graphs Conjecture). For a smallest counterexample, Hall-type exchange arguments show that two maximum stable sets, and likewise two maximum cliques, differ in at most two vertices. A core-corona matching lemma then forces $|\alpha(G)-\omega(G)|\le 2$. Double counting between suitably dense and sparse vertices reduces the problem to twenty-one binary feasibility systems on at most fourteen vertices. Their infeasibility is verified by two independent exact encodings, with a separate exhaustive validation of the forbidden-family constraints.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

[1]

A survey of Nordhaus–Gaddum type relations

Mustapha Aouchiche and Pierre Hansen. A survey of Nordhaus–Gaddum type relations. Discrete Applied Mathematics, 161(4–5):466–546, 2013. doi: 10.1016/j.dam.2011.12.018. URL https://doi.org/10.1016/j.dam.2011.12.018

work page doi:10.1016/j.dam.2011.12.018 2013
[2]

SIAM, DOI 10.1137/1.9780898719796

Andreas Brandst¨ adt, Van Bang Le, and Jeremy P. Spinrad.Graph Classes: A Survey, volume 3 ofSIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia, 1999. doi: 10.1137/1.9780898719796. URL https://doi.org/10.1137/1.9780898719796. 6

work page doi:10.1137/1.9780898719796 1999
[3]

Chudnovsky, N

Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas. The strong perfect graph theorem.Annals of Mathematics, 164(1):51–229, 2006. doi: 10.4007/annals.2006.164.51. URLhttps://doi.org/10.4007/annals.2006.164.51

work page doi:10.4007/annals.2006.164.51 2006
[4]

, TITLE =

Jack Edmonds. Paths, trees, and flowers.Canadian Journal of Mathematics, 17:449–467, 1965. doi: 10.4153/CJM-1965-045-4. URLhttps://doi.org/10.4153/CJM-1965-045-4

work page doi:10.4153/cjm-1965-045-4 1965
[5]

St´ ephane F¨ oldes and Peter L. Hammer. Split graphs having Dilworth number two.Canadian Journal of Mathematics, 29(3):666–672, 1977. doi: 10.4153/CJM-1977-069-1. URL https: //doi.org/10.4153/CJM-1977-069-1

work page doi:10.4153/cjm-1977-069-1 1977
[6]

St´ ephane F¨ oldes and Peter L. Hammer. Split graphs. InProceedings of the Eighth Southeast- ern Conference on Combinatorics, Graph Theory and Computing, volume 19 ofCongressus Numerantium, pages 311–315. Utilitas Mathematica Publishing, 1977

work page 1977
[7]

Elsevier, Amsterdam, second edition, 2004

Martin Charles Golumbic.Algorithmic Graph Theory and Perfect Graphs, volume 57 ofAnnals of Discrete Mathematics. Elsevier, Amsterdam, second edition, 2004

work page 2004
[8]

Polynomial algorithms for perfect graphs

Martin Gr¨ otschel, L´ aszl´ o Lov´ asz, and Alexander Schrijver. Polynomial algorithms for perfect graphs. In Claude Berge and V´ aclav Chv´ atal, editors,Topics on Perfect Graphs, volume 88 of North-Holland Mathematics Studies, pages 325–356. North-Holland, Amsterdam, 1984. doi: 10.1016/S0304-0208(08)72943-8. URL https://doi.org/10.1016/S0304-0208(08)72943-8

work page doi:10.1016/s0304-0208(08)72943-8 1984

Show all 21 references

[9]

On representatives of subsets.Journal of the London Mathematical Society, s1-10(1):26–30, 1935

Philip Hall. On representatives of subsets.Journal of the London Mathematical Society, s1-10(1):26–30, 1935. doi: 10.1112/jlms/s1-10.37.26. URL https://doi.org/10.1112/jlms/ s1-10.37.26

1935 doi
[10]

Hammer and Bruno Simeone

Peter L. Hammer and Bruno Simeone. The splittance of a graph.Combinatorica, 1:275–284,
[11]

Hammer, Toshihide Ibaraki, and Bruno Simeone

Peter L. Hammer, Toshihide Ibaraki, and Bruno Simeone. Threshold sequences.SIAM Journal on Algebraic and Discrete Methods, 2(1):39–49, 1981. doi: 10.1137/0602006. URL https://doi.org/10.1137/0602006

1981 doi
[12]

Hayward, Ch´ ınh T

Ryan B. Hayward, Ch´ ınh T. Ho` ang, and Fr´ ed´ eric Maffray. Optimizing weakly triangulated graphs.Graphs and Combinatorics, 5:339–349, 1989. doi: 10.1007/BF01788689. URL https: //doi.org/10.1007/BF01788689. Erratum: vol. 6 (1990), 33–35, doi:10.1007/BF01787477

1990 doi
[13]

Qi Huangfu and J. A. Julian Hall. Parallelizing the dual revised simplex method.Mathematical Programming Computation, 10(1):119–142, 2018. doi: 10.1007/s12532-017-0130-5. URL https://doi.org/10.1007/s12532-017-0130-5

2018 doi
[14]

Levit, and Eugen Mandrescu

Adi Jarden, Vadim E. Levit, and Eugen Mandrescu. Monotonic properties of collections of max- imum independent sets of a graph.Order, 36:199–207, 2019. doi: 10.1007/s11083-018-9461-8. URLhttps://doi.org/10.1007/s11083-018-9461-8

2019 doi
[15]

Levit and Eugen Mandrescu

Vadim E. Levit and Eugen Mandrescu. A set and collection lemma.The Electronic Journal of Combinatorics, 21(1):P1.40, 2014. doi: 10.37236/2514. URL https://doi.org/10.37236/ 2514

2014 doi
[16]

Polak, and Vaidy Sivaraman

Bart Litjens, Sven C. Polak, and Vaidy Sivaraman. Sum-perfect graphs.Discrete Applied Mathematics, 259:232–239, 2019. doi: 10.1016/j.dam.2018.12.015. URL https://doi.org/10. 1016/j.dam.2018.12.015

2019 doi
[17]

A characterization of perfect graphs.Journal of Combinatorial Theory, Series B, 13(2):95–98, 1972

L´ aszl´ o Lov´ asz. A characterization of perfect graphs.Journal of Combinatorial Theory, Series B, 13(2):95–98, 1972. doi: 10.1016/0095-8956(72)90045-7. URL https://doi.org/10.1016/ 0095-8956(72)90045-7

1972 doi
[18]

E. A. Nordhaus and J. W. Gaddum. On complementary graphs.The American Mathematical Monthly, 63(3):175–177, 1956. doi: 10.2307/2306658. URL https://doi.org/10.2307/ 2306658. 7

1956 doi
[19]

Hereditary Nordhaus–Gaddum graphs.Discrete Applied Mathematics, 367:150–164, 2025

Vaidy Sivaraman and Rebecca Whitman. Hereditary Nordhaus–Gaddum graphs.Discrete Applied Mathematics, 367:150–164, 2025. doi: 10.1016/j.dam.2025.02.010. URL https: //doi.org/10.1016/j.dam.2025.02.010

2025 doi
[20]

SciPy 1.0: Fundamental algorithms for scientific computing in Python

Pauli Virtanen et al. SciPy 1.0: Fundamental algorithms for scientific computing in Python. Nature Methods, 17(3):261–272, 2020. doi: 10.1038/s41592-019-0686-2. URL https://doi. org/10.1038/s41592-019-0686-2. 8

2020 doi
[1981]

URLhttps://doi.org/10.1007/BF02579333

doi: 10.1007/BF02579333. URLhttps://doi.org/10.1007/BF02579333

doi

Pith tools

Reviewed August 27, 2026 · model on record in the stance chip above.

[1] [1]

A survey of Nordhaus–Gaddum type relations

Mustapha Aouchiche and Pierre Hansen. A survey of Nordhaus–Gaddum type relations. Discrete Applied Mathematics, 161(4–5):466–546, 2013. doi: 10.1016/j.dam.2011.12.018. URL https://doi.org/10.1016/j.dam.2011.12.018

work page doi:10.1016/j.dam.2011.12.018 2013

[2] [2]

SIAM, DOI 10.1137/1.9780898719796

Andreas Brandst¨ adt, Van Bang Le, and Jeremy P. Spinrad.Graph Classes: A Survey, volume 3 ofSIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia, 1999. doi: 10.1137/1.9780898719796. URL https://doi.org/10.1137/1.9780898719796. 6

work page doi:10.1137/1.9780898719796 1999

[3] [3]

Chudnovsky, N

Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas. The strong perfect graph theorem.Annals of Mathematics, 164(1):51–229, 2006. doi: 10.4007/annals.2006.164.51. URLhttps://doi.org/10.4007/annals.2006.164.51

work page doi:10.4007/annals.2006.164.51 2006

[4] [4]

, TITLE =

Jack Edmonds. Paths, trees, and flowers.Canadian Journal of Mathematics, 17:449–467, 1965. doi: 10.4153/CJM-1965-045-4. URLhttps://doi.org/10.4153/CJM-1965-045-4

work page doi:10.4153/cjm-1965-045-4 1965

[5] [5]

St´ ephane F¨ oldes and Peter L. Hammer. Split graphs having Dilworth number two.Canadian Journal of Mathematics, 29(3):666–672, 1977. doi: 10.4153/CJM-1977-069-1. URL https: //doi.org/10.4153/CJM-1977-069-1

work page doi:10.4153/cjm-1977-069-1 1977

[6] [6]

St´ ephane F¨ oldes and Peter L. Hammer. Split graphs. InProceedings of the Eighth Southeast- ern Conference on Combinatorics, Graph Theory and Computing, volume 19 ofCongressus Numerantium, pages 311–315. Utilitas Mathematica Publishing, 1977

work page 1977

[7] [7]

Elsevier, Amsterdam, second edition, 2004

Martin Charles Golumbic.Algorithmic Graph Theory and Perfect Graphs, volume 57 ofAnnals of Discrete Mathematics. Elsevier, Amsterdam, second edition, 2004

work page 2004

[8] [8]

Polynomial algorithms for perfect graphs

Martin Gr¨ otschel, L´ aszl´ o Lov´ asz, and Alexander Schrijver. Polynomial algorithms for perfect graphs. In Claude Berge and V´ aclav Chv´ atal, editors,Topics on Perfect Graphs, volume 88 of North-Holland Mathematics Studies, pages 325–356. North-Holland, Amsterdam, 1984. doi: 10.1016/S0304-0208(08)72943-8. URL https://doi.org/10.1016/S0304-0208(08)72943-8

work page doi:10.1016/s0304-0208(08)72943-8 1984