1. Facial colorings using Hall’s Theorem
- Author
-
Frédéric Havet, Daniel Král, Riste Škrekovski, Jean-Sébastien Sereni, 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), 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), Université Nice Sophia Antipolis (... - 2019) (UNS), and 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 (... - 2019) (UNS)
- Subjects
Discrete mathematics ,010102 general mathematics ,0102 computer and information sciences ,Complete coloring ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,01 natural sciences ,Theoretical Computer Science ,Brooks' theorem ,Combinatorics ,Greedy coloring ,Edge coloring ,05C15 ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Graph power ,Computer Science::Computer Vision and Pattern Recognition ,Discrete Mathematics and Combinatorics ,Geometry and Topology ,Graph coloring ,0101 mathematics ,Fractional coloring ,Mathematics ,List coloring - Abstract
International audience; 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.
- Full Text
- View/download PDF