Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

Seminár z teórie grafov - Martin Škoviera (30.3.2023)

vo štvrtok 30.3.2023 o 9:50 hod. v miestnosti M/213

27. 03. 2023 16.18 hod.
Od: Martin Škoviera

Prednášajúci: Martin Škoviera

Názov: Resistance and flow resistance in cubic graphs

Termín: 30.3.2023, 9:50 hod., M 213

We examine the relationship between two measures of uncolourability of cubic graphs -- their resistance and flow resistance. The resistance of a cubic graph G, denoted by r(G), is the minimum number of edges whose removal results in a 3-edge-colourable graph. The flow resistance of G, denoted by r_f(G), is the minimum number of zeroes in a 4-flow on G. Fiol et al. (2018) made a conjecture that r_f(G) never exceeds r(G). We disprove this conjecture by presenting a family of cubic graphs G_n with resistance n and flow resistance 2n. We also present another family H_n where resistance is 2 and flow resistance is n, demonstrating that the ratio r_f(G)/r(G) can be arbitrarily large. Members of both families are nontrivial snarks.

The talk is based on joint results with Imran Allie (University of Cape Town) and Edita Macajova.

Stránka seminára