Aarhus Universitets segl

Circuit Splits

Tommy R. Jensen
Onsdag 27. juni 2018 13:15–14:15 Koll. G (1532-214)

Let $G$ be graph and let $C$ be a circuit (a 2-regular connected subgraph) in $G$. Then a split of $C$ is an unordered pair $X$, $Y$ of circuits with the properties:

  1. $E(C)$ is the symmetric difference of $E(X)$ with $E(Y)$, and
  2. every path in $G$ from $V (X)$ to $V (Y)$ intersects $V(X) \cap V(Y)$.

We conjecture that if $G$ is a cubic 3-connected graph, then there exists a split of $C$. This conjecture is motivated by the Cycle Double Cover (CDC) conjecture of Szekeres and Seymour, and by the stronger Fixed Cycle Double Cover (FCDC) conjecture of Goddyn. If the Circuit Split (CS) conjecture holds, then the FCDC conjecture follows, and CDC with it.

This talk mentions some observations on the CS conjecture and a further strengthening, the Fixed Path Circuit Split (FPCS) conjecture. An interesting feature of the FPCS conjecture is that it may be viewed as a combinatorial (and non-planar) version of the Jordan Curve Theorem; thus if true, it may allow additional applications.

T.R. Jensen, Splits of Circuits, Discrete Mathematics 310, 3026–3029, 2010.

Kontakt: Anders Nedergaard Jensen Revideret: 07.10.2019