Seminár z algebratickej teórie grafov - Edita Mačajová (10.11.2017)

v piatok 10.11.2017 o 13:30 hod.v miestnosti M/XI

08. 11. 2017 13.59 hod.
Od: Martin Mačaj

Prednášajúca: Edita Mačajová

Názov: Point-line configurations and conjectures in Graph Theory

Termín: 10.11.2017, 13:30 hod., M/XI (akvárium)

Abstrakt:
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.