83 citations · 346 across the 78 of their papers we have counts for
8 papers · 1 filter
Hypergraph Artificial Benchmark for Community Detection (h-ABCD)
Bogumił Kamiński, Paweł Prałat, François Théberge
The Artificial Benchmark for Community Detection (ABCD) graph is a recently introduced random graph model with community structure and power-law distribution for both degrees and c…
Almost all 9-regular graphs have a modulo-5 orientation
Michelle Delcourt, Reaz Huq, Pawel Pralat
In 1972 Tutte famously conjectured that every 4-edge-connected graph has a nowhere zero 3-flow; this is known to be equivalent to every 5-regular, 4-edge-connected graph having an…
Rainbow spanning trees in randomly coloured
Deepak Bal, Alan Frieze, Pawel Pralat
Given a graph on vertices and an assignment of colours to its edges, a set of edges is said to be rainbow if edges from have pairwise different co…
The Erdős-Gyárfás function -- so Gyárfás was right
Patrick Bennett, Ryan Cushman, Andrzej Dudek +1
A -coloring of is an edge-coloring of where every -clique spans at least five colors. We show that there exist -colorings of using $\frac 56 n…
A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process
Pu Gao, Calum MacRury, Pawel Pralat
The semi-random graph process is a single player game in which the player is initially presented an empty graph on vertices. In each round, a vertex is presented to the pla…
Modularity of the ABCD Random Graph Model with Community Structure
Bogumil Kaminski, Bartosz Pankratz, Pawel Pralat +1
The Artificial Benchmark for Community Detection (ABCD) graph is a random graph model with community structure and power-law distribution for both degrees and community sizes. The…
Properties and Performance of the ABCDe Random Graph Model with Community Structure
Bogumił Kamiński, Tomasz Olczak, Bartosz Pankratz +2
In this paper, we investigate properties and performance of synthetic random graph models with a built-in community structure. Such models are important for evaluating and tuning c…
Edge and Pair Queries -- Random Graphs and Complexity
Dariusz Dereniowski, Przemysław Gordinowicz, Paweł Prałat
We investigate two types of query games played on a graph, pair queries and edge queries. We concentrate on investigating the two associated graph parameters for binomial random gr…