Speaker
Davide MATTIOLO, KU Leuven
Abstract
Given a real number r ≥ 2, a circular nowhere-zero r-flow, or r-CNZF, on a graph G is an assignment f : E(G) → [1, r − 1] and an orientation D of G, such that, for every x ∈ V (G), the sum of incoming flow values equals the sum of outgoing ones in the orientation D. The circular flow number ϕc(G) of G is the least r such that G admits an r-CNZF. It is well known that the study of many flow problems can be reduced to snarks, i.e. 2-connected non-3-edge-colorable cubic graphs.
In 2008, Lukot’ka and Skoviera proved that a snark G on at most 8k + 4 vertices is such that ϕc(G) ≥ 4 + 1/k. A natural question is then the following: let a ∈ {−2, 0, 2, 4}, is there a family {Sk}k≥1 of snarks such that the order of Sk is 8k + a and ϕc(Sk) = 4 + 1/k?
They noticed that the family of Flower snarks provides a positive answer to this problem for a = 4 and asked if their bound is also sharp for the other values of a. In this seminar we show that Lukot’ka and Skoviera’s bound is sharp for a = 2 and we discuss some related open problems.
