| Title: |
Partitioning sparse graphs into an independent set and a graph with bounded size components |
| Authors: |
Choi, Ilkyoo; Dross, François; Ochem, Pascal |
| Contributors: |
Hankuk University of Foreign Studies (HUFS); 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-02990588 ; Discrete Mathematics, 2020, 343 (8), pp.111921. ⟨10.1016/j.disc.2020.111921⟩. |
| Publisher Information: |
CCSD; Elsevier |
| Publication Year: |
2020 |
| Collection: |
Université de Montpellier: HAL |
| Subject Terms: |
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
| Description: |
International audience ; We study the problem of partitioning the vertex set of a given graph so that each part induces a graph with components of bounded order; we are also interested in restricting these components to be paths. In particular, we say a graph G admits an (I, O k)-partition if its vertex set can be partitioned into an independent set and a set that induces a graph with components of order at most k. We prove that every graph G with mad(G) < 5 2 admits an (I, O 3)-partition. This implies that every planar graph with girth at least 10 can be partitioned into an independent set and a set that induces a graph whose components are paths of order at most 3. We also prove that every graph G with mad(G) < 8k 3k+1 = 8 3 1 − 1 3k+1 admits an (I, O k)-partition. This implies that every planar graph with girth at least 9 can be partitioned into an independent set and a set that induces a graph whose components are paths of order at most 9. |
| Document Type: |
article in journal/newspaper |
| Language: |
English |
| DOI: |
10.1016/j.disc.2020.111921 |
| Availability: |
https://hal.science/hal-02990588; https://hal.science/hal-02990588v1/document; https://hal.science/hal-02990588v1/file/1905.02123.pdf; https://doi.org/10.1016/j.disc.2020.111921 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.424CDCEE |
| Database: |
BASE |