On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph (Q1850603): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Ear decompositions of matching covered graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a conjecture of Lovász concerning bricks. II: Bricks of finite characteristic / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal ear decompositions of matching covered graphs and bases for the matching lattice / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Matching theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Matching structure and the matching lattice / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ear Decompositions of Elementary Graphs and GF2-rank of Perfect Matchings / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The two ear theorem on matching-covered graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5524326 / rank | |||
Normal rank |
Latest revision as of 19:11, 4 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph |
scientific article |
Statements
On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph (English)
0 references
10 December 2002
0 references
A matching covered graph is a nontrivial connected graph in which every edge is contained in some perfect matching. A matching covered graph \(G\) is bicritical if, for any two of its vertices \(u\neq v\), the graph \(G-\{u,v\}\) has a perfect matching. Finally, a brick is a 3-connected bicritical graph. In the two parts of the series [here Part I, for Part II see J. Comb. Theory, Ser. B 85, 137-180 (2002; Zbl 1024.05070 below)] it is proved that, if \(G\) is a brick different from \(K_4\), \(\overline{C}_6\) and \(R_8\), that does not have the Petersen graph as its underlying simple graph, then it has two edges \(e\) and \(f\) such that both \(G-e\) and \(G-f\) are matching covered graphs with exactly one brick, with the additional property that, in each case, the underlying simple graph of that one brick is different from the Petersen graph. This answers in the affirmative a conjecture of Lovász, which states that every brick \(G\) different from \(K_4\), \(\overline{C}_6\), and the Petersen graph has an edge \(e\) such that \(G-e\) is a matching covered graph with exactly one brick.
0 references
bicritical graph
0 references
brick
0 references
matching covered graph
0 references
perfect matching
0 references
Petersen graph
0 references
0 references