Zobrazeno 1 - 10
of 165
pro vyhledávání: '"Pirot, François"'
Let $D$ be a digraph. Its acyclic number $\vec{\alpha}(D)$ is the maximum order of an acyclic induced subdigraph and its dichromatic number $\vec{\chi}(D)$ is the least integer $k$ such that $V(D)$ can be partitioned into $k$ subsets inducing acyclic
Externí odkaz:
http://arxiv.org/abs/2403.02298
Given a graph $G$, a vertex-colouring $\sigma$ of $G$, and a subset $X\subseteq V(G)$, a colour $x \in \sigma(X)$ is said to be \emph{odd} for $X$ in $\sigma$ if it has an odd number of occurrences in $X$. We say that $\sigma$ is an \emph{odd colouri
Externí odkaz:
http://arxiv.org/abs/2306.01341
Autor:
Hurley, Eoin, Pirot, François
We analyse uniformly random proper $k$-colourings of sparse graphs with maximum degree $\Delta$ in the regime $\Delta < k\ln k $. This regime corresponds to the lower side of the shattering threshold for random graph colouring, a paradigmatic example
Externí odkaz:
http://arxiv.org/abs/2303.15367
Given a graph $G$, a colouring of $G$ is acyclic if it is a proper colouring of $G$ and every cycle contains at least three colours. Its acyclic chromatic number $\chi_a(G)$ is the minimum $k$ such that there exists a proper $k$-colouring of $G$ with
Externí odkaz:
http://arxiv.org/abs/2211.08417
We analyze the impact of transient and Byzantine faults on the construction of a maximal independent set in a general network. We adapt the self-stabilizing algorithm presented by Turau `for computing such a vertex set. Our algorithm is self-stabiliz
Externí odkaz:
http://arxiv.org/abs/2210.06116
Autor:
Pirot, François, Hurley, Eoin
We give a short proof of a bound on the list chromatic number of graphs $G$ of maximum degree $\Delta$ where each neighbourhood has density at most $d$, namely $\chi_\ell(G) \le (1+o(1)) \frac{\Delta}{\ln \frac{\Delta}{d+1}}$ as $\frac{\Delta}{d+1} \
Externí odkaz:
http://arxiv.org/abs/2109.15215
Autor:
Bonamy, Marthe, Bousquet, Nicolas, Esperet, Louis, Groenland, Carla, Liu, Chun-Hung, Pirot, François, Scott, Alex
The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In this paper, we study the asymptotic dimension of metric spaces generated by graphs and their shortest path metric and show the
Externí odkaz:
http://arxiv.org/abs/2012.02435
In this paper we study fractional coloring from the angle of distributed computing. Fractional coloring is the linear relaxation of the classical notion of coloring, and has many applications, in particular in scheduling. It was proved by Hasemann, H
Externí odkaz:
http://arxiv.org/abs/2012.01752
Autor:
Bonamy, Marthe, Bousquet, Nicolas, Esperet, Louis, Groenland, Carla, Pirot, François, Scott, Alex
The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. When restricted to graphs and their shortest paths metric, the asymptotic dimension can be seen as a large scale version of weak
Externí odkaz:
http://arxiv.org/abs/2007.03582
We develop an algorithmic framework for graph colouring that reduces the problem to verifying a local probabilistic property of the independent sets. With this we give, for any fixed $k\ge 3$ and $\varepsilon>0$, a randomised polynomial-time algorith
Externí odkaz:
http://arxiv.org/abs/2004.07151