22 citations · 60 across the 24 of their papers we have counts for
34 papers
Typical properties of countable graphs: flows and bridges
Robert Šámal, Hadi Zamani
This paper has two aims. First, we study nowhere-zero flows in countably infinite graphs, observing the different roles played by two types of bridge. Second, we ask how typical gr…
Structure of betweenness uniform graphs with low values of betweenness centrality
Babak Ghanbari, David Hartman, Vít Jelínek +3
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 t…
Precoloring extension in planar near-Eulerian-triangulations
Zdeněk Dvořák, Benjamin Moore, Michaela Seifrtová +1
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 thre…
Nowhere-zero 8-flows in cyclically 5-edge-connected, flow-admissible signed graphs
Matt DeVos, Kathryn Nurse, Robert Sámal
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 show…
Bounds on Functionality and Symmetric Difference -- Two Intriguing Graph Parameters
Pavel Dvořák, Lukáš Folwarczný, Michal Opler +3
Functionality () is a graph parameter that generalizes graph degeneracy defined by Alecu et al. [JCTB, 2021]. They research the relation of functionality to many othe…
Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic
Jesse Campion Loth, Kevin Halasz, Tomáš Masařík +2
A random 2-cell embedding of a connected graph in some orientable surface is obtained by choosing a random local rotation around each vertex. Under this setup, the number of fa…