Seminár z teórie grafov - Makuochukwu Felix Oguagbaka (27.11.2025)
vo štvrtok 27.11.2025 o 9:50 hod. v miestnosti M 213
Prednášajúci: Makuochukwu Felix Oguagbaka
Názov prednášky: Perfect versus imperfect matching covers of cubic graphs
Termín: 27.11.2025, 9:50 hod., M 213
Abstrakt:
Given a bridgeless cubic graph G, the four perfect matching defect of G, denoted by dPM(G), is the minimum number of edges of G left uncovered over all sets of four perfect matchings. The defect of a matching is the number of vertices it leaves uncovered divided by two. The four matching cover defect of G, denoted by dM(G), is the minimal sum of defects of matchings over all matching covers of G containing four matchings.
We show that G always has a matching cover containing two perfect and two non-perfect matchings, and that G has a matching cover containing three perfect matchings and one non-perfect matching if and only if the Fan–Raspaud conjecture holds for G. We establish that dM(G) ≤ dPM(G). We show that for each integer k, there exists a nontrivial snark G with dM(G) = dPM(G) = k; that is, there are nontrivial snarks that are far from being coverable by four perfect matchings. Furthermore, we present another family of nontrivial snarks, where for each integer k there exists a nontrivial snark G with 2dM(G) ≤ dPM(G) = 2k. We conclude this talk with a discussion of open problems.
This is a joint work with Robert Lukoťka.