Zobrazeno 1 - 8
of 8
pro vyhledávání: '"Dujmovi��, Vida"'
Autor:
Akitaya, Hugo A., Dujmovi, Vida, Eppstein, David, Hull, Thomas C., Jain, Kshitij, Lubiw, Anna
Publikováno v:
Journal of Computational Geometry, Vol. 11, No. 1, 2020, pages 397-417
Given a flat-foldable origami crease pattern $G=(V,E)$ (a straight-line drawing of a planar graph on a region of the plane) with a mountain-valley (MV) assignment $\mu:E\to\{-1,1\}$ indicating which creases in $E$ bend convexly (mountain) or concavel
Externí odkaz:
http://arxiv.org/abs/1910.05667
The odd colouring number is a new graph parameter introduced by Petru\v{s}evski and \v{S}krekovski. In this note, we show that graphs with so called product structure have bounded odd-colouring number. By known results on the product structure of $k$
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::34fd1cd78cbba0b999f56da18e4ace94
http://arxiv.org/abs/2202.12882
http://arxiv.org/abs/2202.12882
Motivated by the question of whether planar graphs have bounded queue-number, we prove that planar graphs with maximum degree $\Delta$ have queue-number $O(\Delta^{2})$, which improves upon the best previous bound of $O(\Delta^6)$. More generally, we
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5aecf792564d9cc04c96a79368aaef61
http://arxiv.org/abs/1901.05594
http://arxiv.org/abs/1901.05594
The crossing number of a graph is the minimum number of crossings in a drawing of the graph in the plane. Our main result is that every graph $G$ that does not contain a fixed graph as a minor has crossing number $O(\Delta n)$, where $G$ has $n$ vert
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7496746e7d0867cd11a6358755f522e7
http://arxiv.org/abs/1807.11617
http://arxiv.org/abs/1807.11617
The anagram-free chromatic number is a new graph parameter introduced independently Kam\v{c}ev, {\L}uczak, and Sudakov (2017) and Wilson and Wood (2017). In this note, we show that there are planar graphs of pathwidth 3 with arbitrarily large anagram
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ba7365364f9ba1905234e42b07cd257f
http://arxiv.org/abs/1802.01646
http://arxiv.org/abs/1802.01646
We study the height of a spanning tree $T$ of a graph $G$ obtained by starting with a single vertex of $G$ and repeatedly selecting, uniformly at random, an edge of $G$ with exactly one endpoint in $T$ and adding this edge to $T$.
Updated grant
Updated grant
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7ca57392c2abbdd3f7f5ac67143205ea
http://arxiv.org/abs/1707.00083
http://arxiv.org/abs/1707.00083
Autor:
Aronov, Boris, Dujmovi��, Vida, Morin, Pat, Ooms, Aur��lien, da Silveira, Lu��s Fernando Schultz Xavier
We study the following family of problems: Given a set of $n$ points in convex position, what is the maximum number triangles one can create having these points as vertices while avoiding certain sets of forbidden configurations. As forbidden configu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::97470a7c203d445c4119aee2a2bb12ef
Bourgain and Yehudayoff recently constructed $O(1)$-monotone bipartite expanders. By combining this result with a generalisation of the unraveling method of Kannan, we construct 3-monotone bipartite expanders, which is best possible. We then show tha
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::24ed3228057624f2a1bd5a3b8f94414e
http://arxiv.org/abs/1501.05020
http://arxiv.org/abs/1501.05020