Published April 2010
| Version v1
Journal article
Facial colorings using Hall's Theorem
Contributors
Others:
- Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED) ; Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
- Institut teoretické informatiky (ITI) ; Charles University [Prague] (CU)
- Department of Applied Mathematics (KAM) (KAM) ; Univerzita Karlova v Praze
- Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA) ; Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)
- Faculty of Mathematics and Physics [Ljubljana] (FMF) ; University of Ljubljana
- Égide eco-net project 16305SB
- European Project: 224548,EC:FP7:ICT,FP7-ICT-2007-2,AEOLUS(2008)
Description
A vertex coloring of a plane graph is ℓ-facial if every two distinct vertices joined by a facial walk of length at most ℓ receive distinct colors. It has been conjectured that every plane graph has an ℓ-facial coloring with at most 3ℓ+1 colors. We improve the currently best known bound and show that every plane graph has an ℓ-facial coloring with at most 7ℓ/2+6 colors. Our proof uses the standard discharging technique, however, in the reduction part we have successfully applied Hall's Theorem, which seems to be quite an unusual approach in this area.
Abstract
International audienceAdditional details
Identifiers
- URL
- https://hal.archives-ouvertes.fr/hal-00487100
- URN
- urn:oai:HAL:hal-00487100v1
Origin repository
- Origin repository
- UNICA