Zobrazeno 1 - 10
of 88
pro vyhledávání: '"Sámal, Robert"'
The $k$-th exact-distance graph, of a graph $G$ has $V(G)$ as its vertex set, and $xy$ as an edge if and only if the distance between $x$ and $y$ is (exactly) $k$ in $G$. We consider two possible extensions of this notion for signed graphs. Finding t
Externí odkaz:
http://arxiv.org/abs/2406.10780
This work deals with undirected graphs that have the same betweenness centrality for each vertex, so-called betweenness uniform graphs (or BUGs). The class of these graphs is not trivial and its classification is still an open problem. Recently, Gago
Externí odkaz:
http://arxiv.org/abs/2401.00347
We consider the 4-precoloring extension problem in \emph{planar near-Eulerian-triangulations}, i.e., plane graphs where all faces except possibly for the outer one have length three, all vertices not incident with the outer face have even degree, and
Externí odkaz:
http://arxiv.org/abs/2312.13061
In 1983, Bouchet proved that every bidirected graph with a nowhere-zero integer-flow has a nowhere-zero 216-flow, and conjectured that 216 could be replaced with 6. This paper shows that for cyclically 5-edge-connected bidirected graphs that number c
Externí odkaz:
http://arxiv.org/abs/2309.00704
Autor:
Hušek, Radek, Šámal, Robert
We study a counting version of Cycle Double Cover Conjecture. We discuss why it is more interesting to count circuits (i.e., graphs isomorphic to $C_k$ for some $k$) instead of cycles (graphs with all degrees even). We give an almost-exponential lowe
Externí odkaz:
http://arxiv.org/abs/2303.10615
[Alecu et al.: Graph functionality, JCTB2021] define functionality, a graph parameter that generalizes graph degeneracy. They research the relation of functionality to many other graph parameters (tree-width, clique-width, VC-dimension, etc.). Extend
Externí odkaz:
http://arxiv.org/abs/2302.11862
Publikováno v:
Proceedings: ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
A random 2-cell embedding of a connected graph $G$ in some orientable surface is obtained by choosing a random local rotation around each vertex. Under this setup, the number of faces or the genus of the corresponding 2-cell embedding becomes a rando
Externí odkaz:
http://arxiv.org/abs/2211.01032
Stanislaw Ulam asked whether there exists a universal countable planar graph (that is, a countable planar graph that contains every countable planar graph as a subgraph). J\'anos Pach (1981) answered this question in the negative. We strengthen this
Externí odkaz:
http://arxiv.org/abs/2109.00327
Publikováno v:
Proceedings of the American Mathematical Society 150(9), 3699-3713, 2022; Proceedings: European Conference of Combinatorics, Graph Theory and Applications, EUROCOMB 2021
Random 2-cell embeddings of a given graph $G$ are obtained by choosing a random local rotation around every vertex. We analyze the expected number of faces, $\mathbb{E}[F_G]$, of such an embedding which is equivalent to studying its average genus. So
Externí odkaz:
http://arxiv.org/abs/2103.05036
Autor:
Feghali, Carl, Šámal, Robert
We strengthen a result of Dross, Montassier and Pinlou (2017) that the vertex set of every triangle-free planar graph can be decomposed into a set that induces a forest and a set that induces a forest with maximum degree at most $5$, showing that $5$
Externí odkaz:
http://arxiv.org/abs/2012.15100