|
|||||
|
|
Parity vertex colouring of plane graphs |
|
| Authors: | Július Czap Stanislav Jendro? Margit Voigt |
| Institution: | aDepartment of Applied Mathematics and Business Informatics, Faculty of Economics, Technical University of Košice, B. Němcovej 32, 040 01 Košice, Slovakia;bInstitute of Mathematics, Faculty of Science, Pavol Jozef Šafárik University, Jesenná 5, 040 01 Košice, Slovakia;cFaculty for Information Technology and Mathematics, University of Applied Sciences, Friedrich-List-Platz 1, D-01069 Dresden, Germany |
| Abstract: | A proper vertex colouring of a 2-connected plane graph G is a parity vertex colouring if for each face f and each colour c, either no vertex or an odd number of vertices incident with f is coloured with c. The minimum number of colours used in such a colouring of G is denoted by χp(G).In this paper, we prove that χp(G)≤118 for every 2-connected plane graph G. |
| Keywords: | Discharging method Plane graph Vertex colouring Parity vertex colouring |
| 本文献已被 ScienceDirect 等数据库收录！ | |