Bords amovibles dans des briques presque bipartites

Un bord e d'un graphe couvert par un appariement G est amovible si G-e est également couvert par un appariement. La notion de bord amovible intervient en relation avec des décompositions en oreilles des graphes couverts par un appariement introduites par Lovász et Plummer. Un graphe G couvert par un appariement non bipartite est une brique s'il est exempt de coupes serrées non triviales. Carvalho, Lucchesi et Murty ont prouvé que chaque brique autre que K₄ et C₆ possède au moins -2 bords amovibles. Une brique G est presque bipartite si elle possède une paire de bords \e₁, e₂\ telle que G-\e₁, e₂\ est un graphe couvert par un appariement bipartite. Dans cet article, nous montrons que dans une brique presque bipartite G avec au moins six sommets, chaque sommet de G, sauf au plus six sommets de degré trois contenus dans deux triangles disjoints, est incident avec au plus deux bords non amovibles ; en conséquence, G a au moins |V (G)| - 62 bords amovibles. De plus, tous les graphes atteignant cette borne inférieure sont caractérisés.