Škoviera, Martin; Matematični kolokvij februar 2007

Iz MaFiRaWiki

Graphs, colourings, configurations

Martin Škoviera

Univerza Komenskega, Bratislava, Slovaška

22. februar 2007


Edge colourings of cubic (trivalent) graphs were first considered by Tait in 1880 in his attempt to solve the Four Colour Problem. Since then, they have played an important role in various areas of combinatorics and even beyond. In particular, graphs that are not Tait-colourable are vital for understanding several long-standing conjectures such as the Cycle Double Cover Conjecture, P = NP, Fulkerson's Conjecture, and others.

In this talk we develop the idea of a "local Tait colouring" which may use an unlimited number of colours subject to the condition that the colours of any two edges meeting at a vertex always determine the same third colour. We analyse this definition from a geometric viewpoint: we regard colours as points and place na line through a pair of points whenever the colours meet at some vertex. Two geometries naturally arise in our study, the projective plane PG(2, 2) (the Fano plane) and the affine plane AG(2, 3). We establish a certain correspondence between point-line configurations in the Fano plane and in the affine plane and discuss its consequences.

Finally, we show that three well-known conjectures in graph theory, including the 5-Cycle Double Cover Conjecture, can be formulated in terms of local Tait colourings which employ famous geometric configurations such as the Desargues Configuration (103) and the Cremona-Richmond Configuration (153).


Glej tudi

Matematični kolokviji

Osebna orodja