---
OA_place: publisher
OA_type: hybrid
_id: '18478'
abstract:
- lang: eng
text: For a given graph G=(V,E), we define its \emph{nth subdivision} as the graph
obtained from G by replacing every edge by a path of length n. We also define
the \emph{mth power} of G as the graph on vertex set V where we connect every
pair of vertices at distance at most m in G. In this paper, we study the chromatic
number of powers of subdivisions of graphs and resolve the case m=n asymptotically.
In particular, our result confirms a conjecture of Mozafari-Nia and Iradmusa in
the case m=n=3 in a strong sense.
acknowledgement: "This work was initiated at the annual workshop of the Combinatorics
and Graph Theory group of Freie Universität Berlin in Wilhelmsaue in September 2023.
The authors would like to thank the institution for enabling this research. Finally,
the fourth author would like to thank Tibor Szabó and the Combinatorics and Graph
Theory group at Freie Universität Berlin for their hospitality during the research
visit. Additionally, we thank Moharram Iradmusa for bringing the papers [5], [7]
to our attention. Finally, we thank the anonymous referees for their suggestions
on the manuscript, which have improved the quality of the document.\r\nM.A.: This
project has received funding from the European Union’s Horizon 2020 research and
innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413
.\r\nS.B.: The research leading to these results was supported by EPSRC, UK, grant
no. EP/V048287/1. There are no additional data beyond that contained within the
main manuscript.\r\nS.R.: Funded by the Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) under Germany’s Excellence Strategy – The Berlin Mathematics
Research Center MATH+ (EXC-2046/1, project ID: 390685689).\r\nJ.R. acknowledges
the support of the Grant PID2020-113082GB-I00 funded by MICIU/AEI/10.13039/501100011033,
Spain, and the Severo Ochoa and María de Maeztu Program for Centers and Units of
Excellence in R&D, Spain (CEX2020-001084-M)."
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- first_name: Simona
full_name: Boyadzhiyska, Simona
last_name: Boyadzhiyska
- first_name: Silas
full_name: Rathke, Silas
last_name: Rathke
- first_name: Juanjo
full_name: Rué, Juanjo
last_name: Rué
citation:
ama: Anastos M, Boyadzhiyska S, Rathke S, Rué J. On the chromatic number of powers
of subdivisions of graphs. Discrete Applied Mathematics. 2025;360:506-511.
doi:10.1016/j.dam.2024.10.002
apa: Anastos, M., Boyadzhiyska, S., Rathke, S., & Rué, J. (2025). On the chromatic
number of powers of subdivisions of graphs. Discrete Applied Mathematics.
Elsevier. https://doi.org/10.1016/j.dam.2024.10.002
chicago: Anastos, Michael, Simona Boyadzhiyska, Silas Rathke, and Juanjo Rué. “On
the Chromatic Number of Powers of Subdivisions of Graphs.” Discrete Applied
Mathematics. Elsevier, 2025. https://doi.org/10.1016/j.dam.2024.10.002.
ieee: M. Anastos, S. Boyadzhiyska, S. Rathke, and J. Rué, “On the chromatic number
of powers of subdivisions of graphs,” Discrete Applied Mathematics, vol.
360. Elsevier, pp. 506–511, 2025.
ista: Anastos M, Boyadzhiyska S, Rathke S, Rué J. 2025. On the chromatic number
of powers of subdivisions of graphs. Discrete Applied Mathematics. 360, 506–511.
mla: Anastos, Michael, et al. “On the Chromatic Number of Powers of Subdivisions
of Graphs.” Discrete Applied Mathematics, vol. 360, Elsevier, 2025, pp.
506–11, doi:10.1016/j.dam.2024.10.002.
short: M. Anastos, S. Boyadzhiyska, S. Rathke, J. Rué, Discrete Applied Mathematics
360 (2025) 506–511.
corr_author: '1'
date_created: 2024-10-27T23:01:44Z
date_published: 2025-01-15T00:00:00Z
date_updated: 2025-04-14T07:54:56Z
day: '15'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1016/j.dam.2024.10.002
ec_funded: 1
external_id:
arxiv:
- '2404.05542'
isi:
- '001343647000001'
file:
- access_level: open_access
checksum: bd20a13e56b3ea01daf5e7aca5247c60
content_type: application/pdf
creator: dernst
date_created: 2025-01-13T09:25:59Z
date_updated: 2025-01-13T09:25:59Z
file_id: '18836'
file_name: 2025_DiscreteApplMath_Anastos.pdf
file_size: 441060
relation: main_file
success: 1
file_date_updated: 2025-01-13T09:25:59Z
has_accepted_license: '1'
intvolume: ' 360'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '01'
oa: 1
oa_version: Published Version
page: 506-511
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: Discrete Applied Mathematics
publication_identifier:
issn:
- 0166-218X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the chromatic number of powers of subdivisions of graphs
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 360
year: '2025'
...
---
_id: '8793'
abstract:
- lang: eng
text: We study optimal election sequences for repeatedly selecting a (very) small
group of leaders among a set of participants (players) with publicly known unique
ids. In every time slot, every player has to select exactly one player that it
considers to be the current leader, oblivious to the selection of the other players,
but with the overarching goal of maximizing a given parameterized global (“social”)
payoff function in the limit. We consider a quite generic model, where the local
payoff achieved by a given player depends, weighted by some arbitrary but fixed
real parameter, on the number of different leaders chosen in a round, the number
of players that choose the given player as the leader, and whether the chosen
leader has changed w.r.t. the previous round or not. The social payoff can be
the maximum, average or minimum local payoff of the players. Possible applications
include quite diverse examples such as rotating coordinator-based distributed
algorithms and long-haul formation flying of social birds. Depending on the weights
and the particular social payoff, optimal sequences can be very different, from
simple round-robin where all players chose the same leader alternatingly every
time slot to very exotic patterns, where a small group of leaders (at most 2)
is elected in every time slot. Moreover, we study the question if and when a single
player would not benefit w.r.t. its local payoff when deviating from the given
optimal sequence, i.e., when our optimal sequences are Nash equilibria in the
restricted strategy space of oblivious strategies. As this is the case for many
parameterizations of our model, our results reveal that no punishment is needed
to make it rational for the players to optimize the social payoff.
acknowledgement: "We are grateful to Matthias Függer and Thomas Nowak for having raised
our interest in the problem studied in this paper.\r\nThis work has been supported
the Austrian Science Fund (FWF) projects S11405, S11407 (RiSE), and P28182 (ADynNet)."
article_processing_charge: No
article_type: original
author:
- first_name: Martin
full_name: Zeiner, Martin
last_name: Zeiner
- first_name: Ulrich
full_name: Schmid, Ulrich
last_name: Schmid
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: Zeiner M, Schmid U, Chatterjee K. Optimal strategies for selecting coordinators.
Discrete Applied Mathematics. 2021;289(1):392-415. doi:10.1016/j.dam.2020.10.022
apa: Zeiner, M., Schmid, U., & Chatterjee, K. (2021). Optimal strategies for
selecting coordinators. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2020.10.022
chicago: Zeiner, Martin, Ulrich Schmid, and Krishnendu Chatterjee. “Optimal Strategies
for Selecting Coordinators.” Discrete Applied Mathematics. Elsevier, 2021.
https://doi.org/10.1016/j.dam.2020.10.022.
ieee: M. Zeiner, U. Schmid, and K. Chatterjee, “Optimal strategies for selecting
coordinators,” Discrete Applied Mathematics, vol. 289, no. 1. Elsevier,
pp. 392–415, 2021.
ista: Zeiner M, Schmid U, Chatterjee K. 2021. Optimal strategies for selecting coordinators.
Discrete Applied Mathematics. 289(1), 392–415.
mla: Zeiner, Martin, et al. “Optimal Strategies for Selecting Coordinators.” Discrete
Applied Mathematics, vol. 289, no. 1, Elsevier, 2021, pp. 392–415, doi:10.1016/j.dam.2020.10.022.
short: M. Zeiner, U. Schmid, K. Chatterjee, Discrete Applied Mathematics 289 (2021)
392–415.
corr_author: '1'
date_created: 2020-11-22T23:01:26Z
date_published: 2021-01-31T00:00:00Z
date_updated: 2026-04-16T09:15:13Z
day: '31'
ddc:
- '510'
department:
- _id: KrCh
doi: 10.1016/j.dam.2020.10.022
external_id:
isi:
- '000596823800035'
file:
- access_level: open_access
checksum: f1039ff5a2d6ca116720efdb84ee9d5e
content_type: application/pdf
creator: dernst
date_created: 2021-02-04T11:28:42Z
date_updated: 2021-02-04T11:28:42Z
file_id: '9089'
file_name: 2021_DiscreteApplMath_Zeiner.pdf
file_size: 652739
relation: main_file
success: 1
file_date_updated: 2021-02-04T11:28:42Z
has_accepted_license: '1'
intvolume: ' 289'
isi: 1
issue: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 392-415
project:
- _id: 25F2ACDE-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Rigorous Systems Engineering
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: Discrete Applied Mathematics
publication_identifier:
eissn:
- 1872-6771
issn:
- 0166-218X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Optimal strategies for selecting coordinators
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: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 289
year: '2021'
...
---
_id: '5857'
abstract:
- lang: eng
text: 'A thrackle is a graph drawn in the plane so that every pair of its edges
meet exactly once: either at a common end vertex or in a proper crossing. We prove
that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are
defined similarly, except that every pair of edges that do not share a vertex
are allowed to cross an odd number of times. It is also shown that the maximum
number of edges of a quasi-thrackle on n vertices is [Formula presented](n−1),
and that this bound is best possible for infinitely many values of n.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: János
full_name: Pach, János
last_name: Pach
citation:
ama: 'Fulek R, Pach J. Thrackles: An improved upper bound. Discrete Applied Mathematics.
2019;259(4):266-231. doi:10.1016/j.dam.2018.12.025'
apa: 'Fulek, R., & Pach, J. (2019). Thrackles: An improved upper bound. Discrete
Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2018.12.025'
chicago: 'Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.”
Discrete Applied Mathematics. Elsevier, 2019. https://doi.org/10.1016/j.dam.2018.12.025.'
ieee: 'R. Fulek and J. Pach, “Thrackles: An improved upper bound,” Discrete Applied
Mathematics, vol. 259, no. 4. Elsevier, pp. 266–231, 2019.'
ista: 'Fulek R, Pach J. 2019. Thrackles: An improved upper bound. Discrete Applied
Mathematics. 259(4), 266–231.'
mla: 'Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” Discrete
Applied Mathematics, vol. 259, no. 4, Elsevier, 2019, pp. 266–231, doi:10.1016/j.dam.2018.12.025.'
short: R. Fulek, J. Pach, Discrete Applied Mathematics 259 (2019) 266–231.
date_created: 2019-01-20T22:59:17Z
date_published: 2019-04-30T00:00:00Z
date_updated: 2026-04-16T09:48:11Z
day: '30'
department:
- _id: UlWa
doi: 10.1016/j.dam.2018.12.025
external_id:
arxiv:
- '1708.08037'
isi:
- '000466061100020'
intvolume: ' 259'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1708.08037
month: '04'
oa: 1
oa_version: Preprint
page: 266-231
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: Discrete Applied Mathematics
publication_identifier:
issn:
- 0166-218X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '433'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: 'Thrackles: An improved upper bound'
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 259
year: '2019'
...
---
_id: '5799'
abstract:
- lang: eng
text: We construct a polyhedral surface called a graceful surface, which provides
best possible approximation to a given sphere regarding certain criteria. In digital
geometry terms, the graceful surface is uniquely characterized by its minimality
while guaranteeing the connectivity of certain discrete (polyhedral) curves defined
on it. The notion of “gracefulness” was first proposed in Brimkov and Barneva
(1999) and shown to be useful for triangular mesh discretization through graceful
planes and graceful lines. In this paper we extend the considerations to a nonlinear
object such as a sphere. In particular, we investigate the properties of a discrete
geodesic path between two voxels and show that discrete 3D circles, circular arcs,
and Mobius triangles are all constructible on a graceful sphere, with guaranteed
minimum thickness and the desired connectivity in the discrete topological space.
author:
- first_name: Ranita
full_name: Biswas, Ranita
id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
last_name: Biswas
orcid: 0000-0002-5372-7890
- first_name: Partha
full_name: Bhowmick, Partha
last_name: Bhowmick
- first_name: Valentin E.
full_name: Brimkov, Valentin E.
last_name: Brimkov
citation:
ama: Biswas R, Bhowmick P, Brimkov VE. On the polyhedra of graceful spheres and
circular geodesics. Discrete Applied Mathematics. 2017;216:362-375. doi:10.1016/j.dam.2015.11.017
apa: Biswas, R., Bhowmick, P., & Brimkov, V. E. (2017). On the polyhedra of
graceful spheres and circular geodesics. Discrete Applied Mathematics.
Elsevier. https://doi.org/10.1016/j.dam.2015.11.017
chicago: Biswas, Ranita, Partha Bhowmick, and Valentin E. Brimkov. “On the Polyhedra
of Graceful Spheres and Circular Geodesics.” Discrete Applied Mathematics.
Elsevier, 2017. https://doi.org/10.1016/j.dam.2015.11.017.
ieee: R. Biswas, P. Bhowmick, and V. E. Brimkov, “On the polyhedra of graceful spheres
and circular geodesics,” Discrete Applied Mathematics, vol. 216. Elsevier,
pp. 362–375, 2017.
ista: Biswas R, Bhowmick P, Brimkov VE. 2017. On the polyhedra of graceful spheres
and circular geodesics. Discrete Applied Mathematics. 216, 362–375.
mla: Biswas, Ranita, et al. “On the Polyhedra of Graceful Spheres and Circular Geodesics.”
Discrete Applied Mathematics, vol. 216, Elsevier, 2017, pp. 362–75, doi:10.1016/j.dam.2015.11.017.
short: R. Biswas, P. Bhowmick, V.E. Brimkov, Discrete Applied Mathematics 216 (2017)
362–375.
date_created: 2019-01-08T20:41:12Z
date_published: 2017-01-10T00:00:00Z
date_updated: 2021-01-12T08:03:33Z
day: '10'
doi: 10.1016/j.dam.2015.11.017
extern: '1'
intvolume: ' 216'
language:
- iso: eng
month: '01'
oa_version: None
page: 362-375
publication: Discrete Applied Mathematics
publication_identifier:
issn:
- 0166-218X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
status: public
title: On the polyhedra of graceful spheres and circular geodesics
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 216
year: '2017'
...
---
_id: '4013'
abstract:
- lang: eng
text: The shape of a protein is important for its functions, This includes the location
and size of identifiable regions in its complement space. We formally define pockets
as regions in the complement with limited accessibility from the outside. Pockets
can be efficiently constructed by an algorithm based on alpha complexes. The algorithm
is implemented and applied to proteins with known three-dimensional conformations.
1998 Published by Elsevier Science B.V. All rights reserved.
acknowledgement: 'The authors thank Ping Fu and Ernst Miicke for their contributions
to the alpha shapes software in which the pockets software is embedded. '
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: Michael
full_name: Facello, Michael
last_name: Facello
- first_name: Jie
full_name: Liang, Jie
last_name: Liang
citation:
ama: Edelsbrunner H, Facello M, Liang J. On the definition and the construction
of pockets in macromolecules. Discrete Applied Mathematics. 1998;88(1-3):83-102.
doi:10.1016/S0166-218X(98)00067-5
apa: Edelsbrunner, H., Facello, M., & Liang, J. (1998). On the definition and
the construction of pockets in macromolecules. Discrete Applied Mathematics.
Elsevier. https://doi.org/10.1016/S0166-218X(98)00067-5
chicago: Edelsbrunner, Herbert, Michael Facello, and Jie Liang. “On the Definition
and the Construction of Pockets in Macromolecules.” Discrete Applied Mathematics.
Elsevier, 1998. https://doi.org/10.1016/S0166-218X(98)00067-5.
ieee: H. Edelsbrunner, M. Facello, and J. Liang, “On the definition and the construction
of pockets in macromolecules,” Discrete Applied Mathematics, vol. 88, no.
1–3. Elsevier, pp. 83–102, 1998.
ista: Edelsbrunner H, Facello M, Liang J. 1998. On the definition and the construction
of pockets in macromolecules. Discrete Applied Mathematics. 88(1–3), 83–102.
mla: Edelsbrunner, Herbert, et al. “On the Definition and the Construction of Pockets
in Macromolecules.” Discrete Applied Mathematics, vol. 88, no. 1–3, Elsevier,
1998, pp. 83–102, doi:10.1016/S0166-218X(98)00067-5.
short: H. Edelsbrunner, M. Facello, J. Liang, Discrete Applied Mathematics 88 (1998)
83–102.
date_created: 2018-12-11T12:06:26Z
date_published: 1998-11-09T00:00:00Z
date_updated: 2022-08-25T15:06:30Z
day: '09'
doi: 10.1016/S0166-218X(98)00067-5
extern: '1'
external_id:
pmid:
- '9390238'
intvolume: ' 88'
issue: 1-3
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/S0166218X98000675?via%3Dihub
month: '11'
oa: 1
oa_version: Published Version
page: 83 - 102
pmid: 1
publication: Discrete Applied Mathematics
publication_identifier:
issn:
- 0166-218X
publication_status: published
publisher: Elsevier
publist_id: '2114'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the definition and the construction of pockets in macromolecules
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 88
year: '1998'
...
---
_id: '4025'
abstract:
- lang: eng
text: Questions of chemical reactivity can often be cast as questions of molecular
geometry. Common geometric models for proteins and other molecules are the space-filling
diagram, the solvent accessible surface and the molecular surface. In this paper
we present a new approach to triangulating the surface of a molecule under the
three models, which is fast, robust, and results in topologically correct triangulations.
Our computations are based on a simplicial complex dual to the molecule models.
All proposed algorithms are parallelizable.
acknowledgement: 'The research of both authors is partially supported by the Office
of Naval Research. Herbert Edelsbrunner is also supported through the Alan T. Waterman
award, grant CCR-9118874. '
article_processing_charge: No
article_type: original
author:
- first_name: Nataraj
full_name: Akkiraju, Nataraj
last_name: Akkiraju
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Akkiraju N, Edelsbrunner H. Triangulating the surface of a molecule. Discrete
Applied Mathematics. 1996;71(1-3):5-22. doi:10.1016/S0166-218X(96)00054-6
apa: Akkiraju, N., & Edelsbrunner, H. (1996). Triangulating the surface of a
molecule. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/S0166-218X(96)00054-6
chicago: Akkiraju, Nataraj, and Herbert Edelsbrunner. “Triangulating the Surface
of a Molecule.” Discrete Applied Mathematics. Elsevier, 1996. https://doi.org/10.1016/S0166-218X(96)00054-6.
ieee: N. Akkiraju and H. Edelsbrunner, “Triangulating the surface of a molecule,”
Discrete Applied Mathematics, vol. 71, no. 1–3. Elsevier, pp. 5–22, 1996.
ista: Akkiraju N, Edelsbrunner H. 1996. Triangulating the surface of a molecule.
Discrete Applied Mathematics. 71(1–3), 5–22.
mla: Akkiraju, Nataraj, and Herbert Edelsbrunner. “Triangulating the Surface of
a Molecule.” Discrete Applied Mathematics, vol. 71, no. 1–3, Elsevier,
1996, pp. 5–22, doi:10.1016/S0166-218X(96)00054-6.
short: N. Akkiraju, H. Edelsbrunner, Discrete Applied Mathematics 71 (1996) 5–22.
date_created: 2018-12-11T12:06:30Z
date_published: 1996-12-05T00:00:00Z
date_updated: 2022-08-09T14:06:12Z
day: '05'
doi: 10.1016/S0166-218X(96)00054-6
extern: '1'
intvolume: ' 71'
issue: 1-3
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/S0166218X96000546?via%3Dihub
month: '12'
oa: 1
oa_version: Published Version
page: 5 - 22
publication: Discrete Applied Mathematics
publication_identifier:
issn:
- 0166-218X
publication_status: published
publisher: Elsevier
publist_id: '2102'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Triangulating the surface of a molecule
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 71
year: '1996'
...