Zobrazeno 1 - 10
of 598
pro vyhledávání: '"Molloy Michael"'
We study a generalisation of Vizing's theorem, where the goal is to simultaneously colour the edges of graphs $G_1,\dots,G_k$ with few colours. We obtain asymptotically optimal bounds for the required number of colours in terms of the maximum degree
Externí odkaz:
http://arxiv.org/abs/2411.04071
We study the 2-offer semirandom 3-uniform hypergraph model on $n$ vertices. At each step, we are presented with 2 uniformly random vertices. We choose any other vertex, thus creating a hyperedge of size 3. We show a strategy that constructs a perfect
Externí odkaz:
http://arxiv.org/abs/2401.00559
The degree-restricted random process is a natural algorithmic model for generating graphs with degree sequence D_n=(d_1, \ldots, d_n): starting with an empty n-vertex graph, it sequentially adds new random edges so that the degree of each vertex v_i
Externí odkaz:
http://arxiv.org/abs/2211.00835
Autor:
Aliaj, Jurgen, Molloy, Michael
The adaptable choosability of a multigraph $G$, denoted $\mathrm{ch}_a(G)$, is the smallest integer $k$ such that any edge labelling, $\tau$, of $G$ and any assignment of lists of size $k$ to the vertices of $G$ permits a list colouring, $\sigma$, of
Externí odkaz:
http://arxiv.org/abs/2107.04253
Autor:
Laman, Jon D.1 j.d.laman@umcg.nl, Molloy, Michael mike.j.molloy@gmail.com, Noelle, Randolph J.2 rjn@dartmouth.edu
Publikováno v:
Science. 8/23/2024, Vol. 385 Issue 6711, p827-829. 3p.
The cochromatic number $Z(G)$ of a graph $G$ is the fewest number of colors needed to color the vertices of $G$ so that each color class is a clique or an independent set. In a fractional cocoloring of $G$ a non-negative weight is assigned to each cl
Externí odkaz:
http://arxiv.org/abs/1906.05504
Autor:
Molloy, Michael, Postle, Luke
We prove that every simple graph with maximum degree $\Delta$ has an edge correspondence colouring with $\Delta+o(\Delta)$ colours.
Externí odkaz:
http://arxiv.org/abs/1808.08594
We prove that $G_{n,p=c/n}$ whp has a $k$-regular subgraph if $c$ is at least $e^{-\Theta(k)}$ above the threshold for the appearance of a subgraph with minimum degree at least $k$; i.e. an non-empty $k$-core. In particular, this pins down the thresh
Externí odkaz:
http://arxiv.org/abs/1804.04173