--- _id: '15163' abstract: - lang: eng text: 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-colouring such graphs. acknowledgement: We wish to thank Dániel Marx and András Sebő for making us aware of the results in [8] and some clarifications on them. article_number: '113962' article_processing_charge: No article_type: original author: - first_name: Rutger full_name: Campbell, Rutger last_name: Campbell - first_name: Florian full_name: Hörsch, Florian last_name: Hörsch - first_name: Benjamin full_name: Moore, Benjamin id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6 last_name: Moore citation: ama: Campbell R, Hörsch F, Moore B. Decompositions into two linear forests of bounded lengths. Discrete Mathematics. 2024;347(6). doi:10.1016/j.disc.2024.113962 apa: Campbell, R., Hörsch, F., & Moore, B. (2024). Decompositions into two linear forests of bounded lengths. Discrete Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2024.113962 chicago: Campbell, Rutger, Florian Hörsch, and Benjamin Moore. “Decompositions into Two Linear Forests of Bounded Lengths.” Discrete Mathematics. Elsevier, 2024. https://doi.org/10.1016/j.disc.2024.113962. ieee: R. Campbell, F. Hörsch, and B. Moore, “Decompositions into two linear forests of bounded lengths,” Discrete Mathematics, vol. 347, no. 6. Elsevier, 2024. ista: Campbell R, Hörsch F, Moore B. 2024. Decompositions into two linear forests of bounded lengths. Discrete Mathematics. 347(6), 113962. mla: Campbell, Rutger, et al. “Decompositions into Two Linear Forests of Bounded Lengths.” Discrete Mathematics, vol. 347, no. 6, 113962, Elsevier, 2024, doi:10.1016/j.disc.2024.113962. short: R. Campbell, F. Hörsch, B. Moore, Discrete Mathematics 347 (2024). date_created: 2024-03-24T23:00:58Z date_published: 2024-03-19T00:00:00Z date_updated: 2024-03-25T08:09:43Z day: '19' department: - _id: MaKw doi: 10.1016/j.disc.2024.113962 external_id: arxiv: - '2301.11615' intvolume: ' 347' issue: '6' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2301.11615 month: '03' oa: 1 oa_version: Preprint publication: Discrete Mathematics publication_identifier: issn: - 0012-365X publication_status: epub_ahead publisher: Elsevier quality_controlled: '1' scopus_import: '1' status: public title: Decompositions into two linear forests of bounded lengths type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 347 year: '2024' ... --- _id: '12680' abstract: - lang: eng text: The celebrated Erdős–Ko–Rado theorem about the maximal size of an intersecting family of r-element subsets of was extended to the setting of exterior algebra in [5, Theorem 2.3] and in [6, Theorem 1.4]. However, the equality case has not been settled yet. In this short note, we show that the extension of the Erdős–Ko–Rado theorem and the characterization of the equality case therein, as well as those of the Hilton–Milner theorem to the setting of exterior algebra in the simplest non-trivial case of two-forms follow from a folklore puzzle about possible arrangements of an intersecting family of lines. article_number: '113363' article_processing_charge: No article_type: letter_note author: - first_name: Grigory full_name: Ivanov, Grigory id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E last_name: Ivanov - first_name: Seyda full_name: Köse, Seyda id: 8ba3170d-dc85-11ea-9058-c4251c96a6eb last_name: Köse citation: ama: Ivanov G, Köse S. Erdős-Ko-Rado and Hilton-Milner theorems for two-forms. Discrete Mathematics. 2023;346(6). doi:10.1016/j.disc.2023.113363 apa: Ivanov, G., & Köse, S. (2023). Erdős-Ko-Rado and Hilton-Milner theorems for two-forms. Discrete Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2023.113363 chicago: Ivanov, Grigory, and Seyda Köse. “Erdős-Ko-Rado and Hilton-Milner Theorems for Two-Forms.” Discrete Mathematics. Elsevier, 2023. https://doi.org/10.1016/j.disc.2023.113363. ieee: G. Ivanov and S. Köse, “Erdős-Ko-Rado and Hilton-Milner theorems for two-forms,” Discrete Mathematics, vol. 346, no. 6. Elsevier, 2023. ista: Ivanov G, Köse S. 2023. Erdős-Ko-Rado and Hilton-Milner theorems for two-forms. Discrete Mathematics. 346(6), 113363. mla: Ivanov, Grigory, and Seyda Köse. “Erdős-Ko-Rado and Hilton-Milner Theorems for Two-Forms.” Discrete Mathematics, vol. 346, no. 6, 113363, Elsevier, 2023, doi:10.1016/j.disc.2023.113363. short: G. Ivanov, S. Köse, Discrete Mathematics 346 (2023). date_created: 2023-02-26T23:01:00Z date_published: 2023-06-01T00:00:00Z date_updated: 2023-10-04T11:54:57Z day: '01' department: - _id: UlWa - _id: GradSch doi: 10.1016/j.disc.2023.113363 external_id: arxiv: - '2201.10892' intvolume: ' 346' issue: '6' language: - iso: eng main_file_link: - open_access: '1' url: ' https://doi.org/10.48550/arXiv.2201.10892' month: '06' oa: 1 oa_version: Preprint publication: Discrete Mathematics publication_identifier: issn: - 0012-365X publication_status: published publisher: Elsevier quality_controlled: '1' related_material: record: - id: '13331' relation: dissertation_contains status: public scopus_import: '1' status: public title: Erdős-Ko-Rado and Hilton-Milner theorems for two-forms type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 346 year: '2023' ... --- _id: '6638' abstract: - lang: eng text: The crossing number of a graph G is the least number of crossings over all possible drawings of G. We present a structural characterization of graphs with crossing number one. article_processing_charge: No author: - first_name: 'André ' full_name: 'Silva, André ' last_name: Silva - first_name: Alan M full_name: Arroyo Guevara, Alan M id: 3207FDC6-F248-11E8-B48F-1D18A9856A87 last_name: Arroyo Guevara orcid: 0000-0003-2401-8670 - first_name: Bruce full_name: Richter, Bruce last_name: Richter - first_name: Orlando full_name: Lee, Orlando last_name: Lee citation: ama: Silva A, Arroyo Guevara AM, Richter B, Lee O. Graphs with at most one crossing. Discrete Mathematics. 2019;342(11):3201-3207. doi:10.1016/j.disc.2019.06.031 apa: Silva, A., Arroyo Guevara, A. M., Richter, B., & Lee, O. (2019). Graphs with at most one crossing. Discrete Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2019.06.031 chicago: Silva, André , Alan M Arroyo Guevara, Bruce Richter, and Orlando Lee. “Graphs with at Most One Crossing.” Discrete Mathematics. Elsevier, 2019. https://doi.org/10.1016/j.disc.2019.06.031. ieee: A. Silva, A. M. Arroyo Guevara, B. Richter, and O. Lee, “Graphs with at most one crossing,” Discrete Mathematics, vol. 342, no. 11. Elsevier, pp. 3201–3207, 2019. ista: Silva A, Arroyo Guevara AM, Richter B, Lee O. 2019. Graphs with at most one crossing. Discrete Mathematics. 342(11), 3201–3207. mla: Silva, André, et al. “Graphs with at Most One Crossing.” Discrete Mathematics, vol. 342, no. 11, Elsevier, 2019, pp. 3201–07, doi:10.1016/j.disc.2019.06.031. short: A. Silva, A.M. Arroyo Guevara, B. Richter, O. Lee, Discrete Mathematics 342 (2019) 3201–3207. date_created: 2019-07-14T21:59:20Z date_published: 2019-11-01T00:00:00Z date_updated: 2023-08-29T06:31:41Z day: '01' department: - _id: UlWa doi: 10.1016/j.disc.2019.06.031 ec_funded: 1 external_id: arxiv: - '1901.09955' isi: - '000486358100025' intvolume: ' 342' isi: 1 issue: '11' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1901.09955 month: '11' oa: 1 oa_version: Preprint page: 3201-3207 project: - _id: 26366136-B435-11E9-9278-68D0E5697425 name: Reglas de Conectividad funcional en el hipocampo - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships publication: Discrete Mathematics publication_identifier: issn: - 0012-365X publication_status: published publisher: Elsevier quality_controlled: '1' scopus_import: '1' status: public title: Graphs with at most one crossing type: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 342 year: '2019' ... --- _id: '4065' abstract: - lang: eng text: We prove that given n⩾3 convex, compact, and pairwise disjoint sets in the plane, they may be covered with n non-overlapping convex polygons with a total of not more than 6n−9 sides, and with not more than 3n−6 distinct slopes. Furthermore, we construct sets that require 6n−9 sides and 3n−6 slopes for n⩾3. The upper bound on the number of slopes implies a new bound on a recently studied transversal problem. acknowledgement: 'The first author acknowledges the support by Amoco Fnd. Fat. Dev. Comput. Sci. l-6-44862. Work on this paper by the second author was supported by a Shell Fellowship in Computer Science. The third author as supported by the office of Naval Research under grant NOOO14-86K-0416. ' article_processing_charge: No article_type: original author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Arch full_name: Robison, Arch last_name: Robison - first_name: Xiao full_name: Shen, Xiao last_name: Shen citation: ama: Edelsbrunner H, Robison A, Shen X. Covering convex sets with non-overlapping polygons. Discrete Mathematics. 1990;81(2):153-164. doi:10.1016/0012-365X(90)90147-A apa: Edelsbrunner, H., Robison, A., & Shen, X. (1990). Covering convex sets with non-overlapping polygons. Discrete Mathematics. Elsevier. https://doi.org/10.1016/0012-365X(90)90147-A chicago: Edelsbrunner, Herbert, Arch Robison, and Xiao Shen. “Covering Convex Sets with Non-Overlapping Polygons.” Discrete Mathematics. Elsevier, 1990. https://doi.org/10.1016/0012-365X(90)90147-A. ieee: H. Edelsbrunner, A. Robison, and X. Shen, “Covering convex sets with non-overlapping polygons,” Discrete Mathematics, vol. 81, no. 2. Elsevier, pp. 153–164, 1990. ista: Edelsbrunner H, Robison A, Shen X. 1990. Covering convex sets with non-overlapping polygons. Discrete Mathematics. 81(2), 153–164. mla: Edelsbrunner, Herbert, et al. “Covering Convex Sets with Non-Overlapping Polygons.” Discrete Mathematics, vol. 81, no. 2, Elsevier, 1990, pp. 153–64, doi:10.1016/0012-365X(90)90147-A. short: H. Edelsbrunner, A. Robison, X. Shen, Discrete Mathematics 81 (1990) 153–164. date_created: 2018-12-11T12:06:44Z date_published: 1990-04-15T00:00:00Z date_updated: 2022-02-22T15:45:55Z day: '15' doi: 10.1016/0012-365X(90)90147-A extern: '1' intvolume: ' 81' issue: '2' language: - iso: eng main_file_link: - url: https://www.sciencedirect.com/science/article/pii/0012365X9090147A?via%3Dihub month: '04' oa_version: None page: 153 - 164 publication: Discrete Mathematics publication_identifier: eissn: - 1872-681X issn: - 0012-365X publication_status: published publisher: Elsevier publist_id: '2060' quality_controlled: '1' scopus_import: '1' status: public title: Covering convex sets with non-overlapping polygons type: journal_article user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17 volume: 81 year: '1990' ... --- _id: '4107' abstract: - lang: eng text: A set of m planes dissects E3 into cells, facets, edges and vertices. Letting deg(c) be the number of facets that bound a cellc, we give exact and asymptotic bounds on the maximum of ∈cinCdeg(c), if C is a family of cells of the arrangement with fixed cardinality. acknowledgement: 'Research reported in the paper was conducted while the second author was visiting the Technical University of Graz. Support provided by the Technical University for this visit is gratefully acknowledged. ' article_processing_charge: No article_type: original author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: David full_name: Haussler, David last_name: Haussler citation: ama: Edelsbrunner H, Haussler D. The complexity of cells in 3-dimensional arrangements. Discrete Mathematics. 1986;60(C):139-146. doi:10.1016/0012-365X(86)90008-7 apa: Edelsbrunner, H., & Haussler, D. (1986). The complexity of cells in 3-dimensional arrangements. Discrete Mathematics. Elsevier. https://doi.org/10.1016/0012-365X(86)90008-7 chicago: Edelsbrunner, Herbert, and David Haussler. “The Complexity of Cells in 3-Dimensional Arrangements.” Discrete Mathematics. Elsevier, 1986. https://doi.org/10.1016/0012-365X(86)90008-7. ieee: H. Edelsbrunner and D. Haussler, “The complexity of cells in 3-dimensional arrangements,” Discrete Mathematics, vol. 60, no. C. Elsevier, pp. 139–146, 1986. ista: Edelsbrunner H, Haussler D. 1986. The complexity of cells in 3-dimensional arrangements. Discrete Mathematics. 60(C), 139–146. mla: Edelsbrunner, Herbert, and David Haussler. “The Complexity of Cells in 3-Dimensional Arrangements.” Discrete Mathematics, vol. 60, no. C, Elsevier, 1986, pp. 139–46, doi:10.1016/0012-365X(86)90008-7. short: H. Edelsbrunner, D. Haussler, Discrete Mathematics 60 (1986) 139–146. date_created: 2018-12-11T12:06:59Z date_published: 1986-06-01T00:00:00Z date_updated: 2022-02-01T12:44:50Z day: '01' doi: 10.1016/0012-365X(86)90008-7 extern: '1' intvolume: ' 60' issue: C language: - iso: eng month: '06' oa_version: None page: 139 - 146 publication: Discrete Mathematics publication_identifier: eissn: - 1872-681X issn: - 0012-365X publication_status: published publisher: Elsevier publist_id: '2019' quality_controlled: '1' status: public title: The complexity of cells in 3-dimensional arrangements type: journal_article user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17 volume: 60 year: '1986' ...