Prednáška

Abstrakt

We will consider vertex colourings of plane graphs. We say that a face f of a connected plane graph G uses a colour c under a colouring φ k times if this colour appears k times along the facial walk of f. Colourings of graphs embedded on surfaces with face constrains have recently drawn a substantial amount of attention. Two problems of this kind are the following:

Problem 1. A vertex colouring φ is a weak parity vertex colouring of a connected plane graph G if each face of G uses at least one colour an odd number of times. The problem is to determine the minimum number χω(G) of colours used in a such colouring of G.

Problem 2. A vertex colouring φ is a strong parity vertex colouring of a 2-connected plane graph G if for each face f and each colour c, no vertex or an odd number of vertices incident with f are coloured by c. The problem is to find the the minimum number χs(G) of colours used in a such colouring of G.

We will give a survey on results and open problems concerning the above two basic problems and two other related questions. For example we will prove that if G is a 2- connected cubic plane graph then χω(G)≤3. We will show that there is a proper weak parity vertex colouring of 2-connected plane graphs with 4 colours, which is equivalent to the four colour theorem. We shall mention a recent result of T. Kaiser, O. Rucký, R. Škrekovski, and M. Stehlík that there is a proper strong parity vertex colouring of 2-connected plane graphs with at most 300 colours. We will present several families of plane graphs where the constant 300 can be substantially improved.

Videozáznam z prednášky