# A characterization of extremal graphs with no matching-cut

Abstract : A graph is called (matching-)immune if it has no edge cut that is also a matching. Farley and Proskurowski proved that for all immune graphs $G=(V,E)$, $|E|≥\lceil 3(|V|-1)/2\rceil$ , and constructed a large class of immune graphs that attain this lower bound for every value of $|V(G)|$, called $ABC$ graphs. They conjectured that every immune graph that attains this lower bound is an $ABC$ graph. We present a proof of this conjecture.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [1 references]

https://hal.inria.fr/hal-01184354
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 11:37:02 AM
Last modification on : Thursday, May 11, 2017 - 1:02:54 AM
Long-term archiving on: : Sunday, November 15, 2015 - 10:58:45 AM

### File

dmAE0127.pdf
Publisher files allowed on an open archive

### Citation

Paul Bonsma. A characterization of extremal graphs with no matching-cut. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.135-138, ⟨10.46298/dmtcs.3398⟩. ⟨hal-01184354⟩

Record views