Faculty of Mathematics, Physics
and Informatics
Comenius University Bratislava

Seminar of Graph Theory - Martin Škoviera (30.3.2023)

Thursday 30.3.2023 at 9:50, Lecture room M/213

27. 03. 2023 16.24 hod.
By: Martin Škoviera

Martin Škoviera:
Resistance and flow resistance in cubic graphs

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.

More information