6 papers
On the list version of a conjecture of ErdÅs and Neumann-Lara
Ararat Harutyunyan, Lucas Picasarri-Arrieta, Gil Puig i Surroca
The dichromatic number of a digraph , denoted by , is the smallest number of colours required to colour the vertices of such that each colour class induces an acy…
Acyclic sets and colorings in digraphs under restrictions on degrees and cycle lengths
Ararat Harutyunyan, Colin McDiarmid, Gil Puig i Surroca
Given a digraph , we denote by the maximum size of an acyclic set of (i.e. a set of vertices which induces a subdigraph with no directed cycles), and by $\vecÏ(…
-dicolouring of digraphs
Ararat Harutyunyan, Ken-ichi Kawarabayashi, Lucas Picasarri-Arrieta +1
In 1977, Borodin and Kostochka conjectured that every graph with maximum degree is -colourable, unless it contains a clique of size . In 1999, Reed confirmed…
Colouring Complete Multipartite and Kneser-type Digraphs
Ararat Harutyunyan, Gil Puig i Surroca
The dichromatic number of a digraph is the smallest such that can be partitioned into acyclic subdigraphs, and the dichromatic number of an undirected graph is the…
On endomorphism universality of sparse graph classes
Kolja Knauer, Gil Puig i Surroca
We show that every commutative idempotent monoid (a.k.a lattice) is the endomorphism monoid of a subcubic graph. This solves a problem of Babai and Pultr [J. Comb.~Theory, Ser.~B,…
On rigid regular graphs and a problem of Babai and Pultr
Kolja Knauer, Gil Puig i Surroca
A graph is \textit{rigid} if it only admits the identity endomorphism. We show that for every there exist infinitely many mutually rigid -regular graphs of arbitrary od…