Decompositions into two linear forests of bounded lengths
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Rutger Campbell | - |
dc.contributor.author | Hörsch, Florian | - |
dc.contributor.author | Moore, Benjamin | - |
dc.date.accessioned | 2024-04-11T10:30:01Z | - |
dc.date.available | 2024-04-11T10:30:01Z | - |
dc.date.created | 2024-03-25 | - |
dc.date.issued | 2024-06 | - |
dc.identifier.issn | 0012-365X | - |
dc.identifier.uri | https://pr.ibs.re.kr/handle/8788114/15028 | - |
dc.description.abstract | For some k∈Z≥0∪{∞}, we call a linear forest k-bounded if each of its components has at most k edges. We will say a (k,ℓ)-bounded linear forest decomposition of a graph G is a partition of E(G) into the edge sets of two linear forests Fk,Fℓ where Fk is k-bounded and Fℓ is ℓ-bounded. We show that the problem of deciding whether a given graph has such a decomposition is NP-complete if both k and ℓ are at least 2, NP-complete if k≥9 and ℓ=1, and is in P for (k,ℓ)=(2,1). Before this, the only known NP-complete cases were the (2,2) and (3,3) cases. Our hardness result answers a question of Bermond et al. from 1984. We also show that planar graphs of girth at least nine decompose into a linear forest and a matching, which in particular is stronger than 3-edge-coloring such graphs. © 2024 Elsevier B.V. | - |
dc.language | 영어 | - |
dc.publisher | Elsevier BV | - |
dc.title | Decompositions into two linear forests of bounded lengths | - |
dc.type | Article | - |
dc.type.rims | ART | - |
dc.identifier.wosid | 001226893800001 | - |
dc.identifier.scopusid | 2-s2.0-85188078346 | - |
dc.identifier.rimsid | 82777 | - |
dc.contributor.affiliatedAuthor | Rutger Campbell | - |
dc.identifier.doi | 10.1016/j.disc.2024.113962 | - |
dc.identifier.bibliographicCitation | Discrete Mathematics, v.347, no.6 | - |
dc.relation.isPartOf | Discrete Mathematics | - |
dc.citation.title | Discrete Mathematics | - |
dc.citation.volume | 347 | - |
dc.citation.number | 6 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.isOpenAccess | N | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.subject.keywordAuthor | Linear forest | - |
dc.subject.keywordAuthor | Complexity | - |
dc.subject.keywordAuthor | Graph decomposition | - |