---
OA_place: publisher
OA_type: hybrid
_id: '19002'
abstract:
- lang: eng
text: "A k-subcolouring of a graph G is a function f : V (G) → {0,...,k − 1} such
that the set of\r\nvertices coloured i induce a disjoint union of cliques. The
subchromatic number, χsub(G),\r\nis the minimum k such that G admits a k-subcolouring.
Nešetril, ˇ Ossona de Mendez,\r\nPilipczuk, and Zhu (2020), recently raised the
problem of finding tight upper bounds for\r\nχsub(G2) when G is planar. We show
that χsub(G2) ≤ 43 when G is planar, improving\r\ntheir bound of 135. We give
even better bounds when the planar graph G has larger girth.\r\nMoreover, we show
that χsub(G3) ≤ 95, improving the previous bound of 364. For these\r\nwe adapt
some recent techniques of Almulhim and Kierstead (2022), while also extending\r\nthe
decompositions of triangulated planar graphs of Van den Heuvel, Ossona de Mendez,\r\nQuiroz,
Rabinovich and Siebertz (2017), to planar graphs of arbitrary girth. Note that
these\r\ndecompositions are the precursors of the graph product structure theorem
of planar graphs.\r\nWe give improved bounds for χsub(Gp) for all p ≥ 2, whenever
G has bounded treewidth,\r\nbounded simple treewidth, bounded genus, or excludes
a clique or biclique as a minor.\r\nFor this we introduce a family of parameters
which form a gradation between the strong\r\nand the weak colouring numbers. We
give upper bounds for these parameters for graphs\r\ncoming from such classes.\r\nFinally,
we give a 2-approximation algorithm for the subchromatic number of graphs\r\nhaving
a layering in which each layer has bounded cliquewidth and this layering is\r\ncomputable
in polynomial time (like the class of all dth powers of planar graphs, for fixed\r\nd).
This algorithm works even if the power p and the graph G is unknown."
acknowledgement: We thank an anonymous referee for pointing out an error in an earlier
version of Theorem 3.1. We also thank an anonymous referee for pointing out numerous
typos in an earlier version of the paper.
article_number: '114377'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Pedro P.
full_name: Cortés, Pedro P.
last_name: Cortés
- first_name: Pankaj
full_name: Kumar, Pankaj
last_name: Kumar
- first_name: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
- first_name: Patrice
full_name: Ossona de Mendez, Patrice
last_name: Ossona de Mendez
- first_name: Daniel A.
full_name: Quiroz, Daniel A.
last_name: Quiroz
citation:
ama: Cortés PP, Kumar P, Moore B, Ossona de Mendez P, Quiroz DA. Subchromatic numbers
of powers of graphs with excluded minors. Discrete Mathematics. 2025;348(4).
doi:10.1016/j.disc.2024.114377
apa: Cortés, P. P., Kumar, P., Moore, B., Ossona de Mendez, P., & Quiroz, D.
A. (2025). Subchromatic numbers of powers of graphs with excluded minors. Discrete
Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2024.114377
chicago: Cortés, Pedro P., Pankaj Kumar, Benjamin Moore, Patrice Ossona de Mendez,
and Daniel A. Quiroz. “Subchromatic Numbers of Powers of Graphs with Excluded
Minors.” Discrete Mathematics. Elsevier, 2025. https://doi.org/10.1016/j.disc.2024.114377.
ieee: P. P. Cortés, P. Kumar, B. Moore, P. Ossona de Mendez, and D. A. Quiroz, “Subchromatic
numbers of powers of graphs with excluded minors,” Discrete Mathematics,
vol. 348, no. 4. Elsevier, 2025.
ista: Cortés PP, Kumar P, Moore B, Ossona de Mendez P, Quiroz DA. 2025. Subchromatic
numbers of powers of graphs with excluded minors. Discrete Mathematics. 348(4),
114377.
mla: Cortés, Pedro P., et al. “Subchromatic Numbers of Powers of Graphs with Excluded
Minors.” Discrete Mathematics, vol. 348, no. 4, 114377, Elsevier, 2025,
doi:10.1016/j.disc.2024.114377.
short: P.P. Cortés, P. Kumar, B. Moore, P. Ossona de Mendez, D.A. Quiroz, Discrete
Mathematics 348 (2025).
corr_author: '1'
date_created: 2025-02-05T06:51:08Z
date_published: 2025-04-01T00:00:00Z
date_updated: 2025-09-30T10:25:15Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1016/j.disc.2024.114377
external_id:
arxiv:
- '2306.02195'
isi:
- '001401656900001'
file:
- access_level: open_access
checksum: 6723cbb02b6aea0d05f37d167da00c03
content_type: application/pdf
creator: dernst
date_created: 2025-05-05T12:56:12Z
date_updated: 2025-05-05T12:56:12Z
file_id: '19657'
file_name: 2025_DiscreteMath_Cortes.pdf
file_size: 850988
relation: main_file
success: 1
file_date_updated: 2025-05-05T12:56:12Z
has_accepted_license: '1'
intvolume: ' 348'
isi: 1
issue: '4'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
publication: Discrete Mathematics
publication_identifier:
issn:
- 0012-365X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Subchromatic numbers of powers of graphs with excluded minors
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 348
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '22163'
abstract:
- lang: eng
text: "For a field F and integers d and k, a set A ⊆ Fd is called k-nearly orthogonal
if its\r\nmembers are non-self-orthogonal and every k + 1 vectors of A include
an orthogonal pair.\r\nWe prove that for every prime p there exists some δ = δ(p)>
0, such that for every field\r\nF of characteristic p and for all integers k ≥
2 and d ≥ k, there exists a k-nearly orthogonal\r\nset of at least dδ·k/ logk
vectors of Fd. The size of the set is optimal up to the logk term\r\nin the exponent.
We further prove two extensions of this result. In the first, we provide a\r\nlarge
set A of non-self-orthogonal vectors of Fd such that for every two subsets of
A of\r\nsize k+1 each, some vector of one of the subsets is orthogonal to some
vector of the other.\r\nIn the second extension, every k + 1 vectors of the produced
set A include ℓ + 1 pairwise\r\northogonal vectors for an arbitrary fixed integer
1 ≤ ℓ ≤ k. The proofs involve probabilistic\r\nand spectral arguments and the
hypergraph container method"
article_number: '114373'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Ishay
full_name: Haviv, Ishay
last_name: Haviv
- first_name: Sam
full_name: Mattheus, Sam
last_name: Mattheus
- first_name: Aleksa
full_name: Milojević, Aleksa
last_name: Milojević
- first_name: Yuval
full_name: Wigderson, Yuval
id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
last_name: Wigderson
citation:
ama: Haviv I, Mattheus S, Milojević A, Wigderson Y. Larger nearly orthogonal sets
over finite fields. Discrete Mathematics. 2025;348(4). doi:10.1016/j.disc.2024.114373
apa: Haviv, I., Mattheus, S., Milojević, A., & Wigderson, Y. (2025). Larger
nearly orthogonal sets over finite fields. Discrete Mathematics. Elsevier.
https://doi.org/10.1016/j.disc.2024.114373
chicago: Haviv, Ishay, Sam Mattheus, Aleksa Milojević, and Yuval Wigderson. “Larger
Nearly Orthogonal Sets over Finite Fields.” Discrete Mathematics. Elsevier,
2025. https://doi.org/10.1016/j.disc.2024.114373.
ieee: I. Haviv, S. Mattheus, A. Milojević, and Y. Wigderson, “Larger nearly orthogonal
sets over finite fields,” Discrete Mathematics, vol. 348, no. 4. Elsevier,
2025.
ista: Haviv I, Mattheus S, Milojević A, Wigderson Y. 2025. Larger nearly orthogonal
sets over finite fields. Discrete Mathematics. 348(4), 114373.
mla: Haviv, Ishay, et al. “Larger Nearly Orthogonal Sets over Finite Fields.” Discrete
Mathematics, vol. 348, no. 4, 114373, Elsevier, 2025, doi:10.1016/j.disc.2024.114373.
short: I. Haviv, S. Mattheus, A. Milojević, Y. Wigderson, Discrete Mathematics 348
(2025).
das_tickbox: '1'
date_created: 2026-06-29T10:53:05Z
date_published: 2025-04-01T00:00:00Z
date_updated: 2026-07-14T08:17:17Z
day: '01'
doi: 10.1016/j.disc.2024.114373
extern: '1'
external_id:
arxiv:
- '2404.01057'
intvolume: ' 348'
issue: '4'
keyword:
- Nearly orthogonal sets
- Ramsey theory
- Finite fields
language:
- iso: eng
main_file_link:
- open_access: '1'
url: 'https://doi.org/10.48550/arXiv.2404.01057 '
month: '04'
oa: 1
oa_version: Preprint
publication: Discrete Mathematics
publication_identifier:
issn:
- 0012-365X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Larger nearly orthogonal sets over finite fields
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 348
year: '2025'
...
---
_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
arxiv: 1
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).
corr_author: '1'
date_created: 2024-03-24T23:00:58Z
date_published: 2024-06-01T00:00:00Z
date_updated: 2025-09-04T13:10:26Z
day: '01'
department:
- _id: MaKw
doi: 10.1016/j.disc.2024.113962
external_id:
arxiv:
- '2301.11615'
isi:
- '001226893800001'
intvolume: ' 347'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2301.11615
month: '06'
oa: 1
oa_version: Preprint
publication: Discrete Mathematics
publication_identifier:
issn:
- 0012-365X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Decompositions into two linear forests of bounded lengths
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
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
arxiv: 1
author:
- first_name: Grigory
full_name: Ivanov, Grigory
id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
last_name: Ivanov
orcid: 0000-0002-5021-3982
- first_name: Seyda
full_name: Köse, Seyda
id: 8ba3170d-dc85-11ea-9058-c4251c96a6eb
last_name: Köse
orcid: 0009-0008-0457-9730
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).
corr_author: '1'
date_created: 2023-02-26T23:01:00Z
date_published: 2023-06-01T00:00:00Z
date_updated: 2026-04-07T13:29:28Z
day: '01'
department:
- _id: UlWa
- _id: GradSch
doi: 10.1016/j.disc.2023.113363
external_id:
arxiv:
- '2201.10892'
isi:
- '001189844500001'
intvolume: ' 346'
isi: 1
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 346
year: '2023'
...
---
_id: '9098'
abstract:
- lang: eng
text: "We study properties of the volume of projections of the n-dimensional\r\ncross-polytope
$\\crosp^n = \\{ x \\in \\R^n \\mid |x_1| + \\dots + |x_n| \\leqslant 1\\}.$ We
prove that the projection of $\\crosp^n$ onto a k-dimensional coordinate subspace
has the maximum possible volume for k=2 and for k=3.\r\nWe obtain the exact lower
bound on the volume of such a projection onto a two-dimensional plane. Also, we
show that there exist local maxima which are not global ones for the volume of
a projection of $\\crosp^n$ onto a k-dimensional subspace for any n>k⩾2."
acknowledgement: Research was supported by the Russian Foundation for Basic Research,
project 18-01-00036A (Theorems 1.5 and 5.3) and by the Ministry of Education and
Science of the Russian Federation in the framework of MegaGrant no 075-15-2019-1926
(Theorems 1.2 and 7.3).
article_number: '112312'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Grigory
full_name: Ivanov, Grigory
id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
last_name: Ivanov
citation:
ama: Ivanov G. On the volume of projections of the cross-polytope. Discrete Mathematics.
2021;344(5). doi:10.1016/j.disc.2021.112312
apa: Ivanov, G. (2021). On the volume of projections of the cross-polytope. Discrete
Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2021.112312
chicago: Ivanov, Grigory. “On the Volume of Projections of the Cross-Polytope.”
Discrete Mathematics. Elsevier, 2021. https://doi.org/10.1016/j.disc.2021.112312.
ieee: G. Ivanov, “On the volume of projections of the cross-polytope,” Discrete
Mathematics, vol. 344, no. 5. Elsevier, 2021.
ista: Ivanov G. 2021. On the volume of projections of the cross-polytope. Discrete
Mathematics. 344(5), 112312.
mla: Ivanov, Grigory. “On the Volume of Projections of the Cross-Polytope.” Discrete
Mathematics, vol. 344, no. 5, 112312, Elsevier, 2021, doi:10.1016/j.disc.2021.112312.
short: G. Ivanov, Discrete Mathematics 344 (2021).
date_created: 2021-02-07T23:01:12Z
date_published: 2021-05-01T00:00:00Z
date_updated: 2025-07-10T12:01:36Z
day: '01'
department:
- _id: UlWa
doi: 10.1016/j.disc.2021.112312
external_id:
arxiv:
- '1808.09165'
isi:
- '000633365200001'
intvolume: ' 344'
isi: 1
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1808.09165
month: '05'
oa: 1
oa_version: Preprint
publication: Discrete Mathematics
publication_identifier:
issn:
- 0012-365X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the volume of projections of the cross-polytope
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 344
year: '2021'
...
---
_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
arxiv: 1
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: 2025-04-14T07:44:06Z
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'
...