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

Seminar of Graph Theory - Richard Bíró (13.4.2023)

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

11. 04. 2023 09.29 hod.
Od: Martin Škoviera

Richard Bíró:
Hamiltonian cycles in cubic planar bipartite graphs

Barnette's conjecture states that every cubic planar bipartite 3-connected graph is Hamiltonian. Only partial results are known. One approach is to study subgraphs (multipoles) known as reducible configurations. We say that multipole G is reducible to multipole R if every Hamiltonian cycle which passes through R can be extended into G. We present new cubic planar bipartite reducible configurations found with computer search. In addition, we present new infinite class of reducible configurations and prove reducibility to their respective reductors.

This is a joint work with František Kardoš. 

More information