| Title: |
Vertex partitions of ($C 3 , C 4 , C 6$) -free planar graphs |
| Authors: |
Dross, François; Ochem, Pascal |
| Contributors: |
Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S); Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA); Algorithmes, Graphes et Combinatoire (ALGCO); Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM); Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS); ANR-17-CE40-0022,HOSIGRA,Homomorphismes de graphes signés(2017) |
| Source: |
ISSN: 0012-365X ; Discrete Mathematics ; https://hal.science/hal-02990467 ; Discrete Mathematics, 2019, 342 (11), pp.3229-3236. ⟨10.1016/j.disc.2019.07.002⟩. |
| Publisher Information: |
CCSD; Elsevier |
| Publication Year: |
2019 |
| Collection: |
Université de Montpellier: HAL |
| Subject Terms: |
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
| Description: |
International audience ; A graph is (k 1 , k 2)-colorable if its vertex set can be partitioned into a graph with maximum degree at most k 1 and and a graph with maximum degree at most k 2. We show that every (C 3 , C 4 , C 6)-free planar graph is (0, 6)-colorable. We also show that deciding whether a (C 3 , C 4 , C 6)-free planar graph is (0, 3)-colorable is NP-complete. |
| Document Type: |
article in journal/newspaper |
| Language: |
English |
| DOI: |
10.1016/j.disc.2019.07.002 |
| Availability: |
https://hal.science/hal-02990467; https://hal.science/hal-02990467v1/document; https://hal.science/hal-02990467v1/file/1711.08710.pdf; https://doi.org/10.1016/j.disc.2019.07.002 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.94AFC550 |
| Database: |
BASE |