Algebraic Graph Theory Seminar - Edita Mačajová (10.11.2017)
Friday 10.11.2017 at 13:30, Lecture room M/XI
Edita Mačajová:
Point-line configurations and conjectures in Graph Theory
Abstract:
Many open problems in Graph theory can be reduced to the family of cubic graphs, moreover, in a lot of cases it is enough to focus to even smaller set of graphs -- to snarks, which are cubic graphs which do not admit a proper 3-edge-colouring.
A \emph{configuration} $\mathcal{C}=(P,B)$ consists of a finite set $P$ of \emph{points} and a finite set $B$ of blocks. \emph{Blocks} are 3-element subsets of $P$ such that for each pair of pints of $P$ there is at most one block in $B$ which contains both of them.
A colouring of a cubic graph $G$ with a configuration $\mathcal{C}=(P,B)$ is an assignment of an element from $P$ to each edge of $G$ such that the three points that meet at any vertex form a block of $B$.
During this talk we will discuss several well known conjectures and open problems from the view of colouring with configurations and thereby provide an unifying view of them.
These problems include the Fulkerson Conjecture and the Petersen Coloring Conjecture, the Fan-Raspaud Conjecture, problems concerting the perfect matching index of a graph and others.