On the Strong Parity Chromatic Number

Július Czap 1 Stanislav Jendrol' 2 František Kardoš 2, 3
3 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A vertex colouring of a 2-connected plane graph G is a strong parity vertex colouring if for every face f and each colour c, the number of vertices incident with f coloured by c is either zero or odd. Czap et al. [Discrete Math. 311 (2011) 512-520] proved that every 2-connected plane graph has a proper strong parity vertex colouring with at most 118 colours. In this paper we improve this upper bound for some classes of plane graphs.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/inria-00634956
Contributor : František Kardoš <>
Submitted on : Wednesday, November 9, 2011 - 1:52:04 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Document(s) archivé(s) le : Friday, February 10, 2012 - 2:21:20 AM

File

CJKa11.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00634956, version 1

Collections

Citation

Július Czap, Stanislav Jendrol', František Kardoš. On the Strong Parity Chromatic Number. Discussiones Mathematicae Graph Theory, University of Zielona Góra, 2011, 31 (3), pp.587-600. ⟨inria-00634956⟩

Share

Metrics

Record views

258

Files downloads

141