---
_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'
...