15 citations · 57 across the 24 of their papers we have counts for
18 papers · 1 filter
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 acyc…
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χ(D)…
-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 th…
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…
Domination and fractional domination in digraphs
Ararat Harutyunyan, Tien-Nam Le, Alantha Newman +1
In this paper, we investigate the relation between the (fractional) domination number of a digraph and the independence number of its underlying graph, denoted by . More…
Coloring dense digraphs
Ararat Harutyunyan, Tien-Nam Le, Alantha Newman +1
The chromatic number of a digraph is the minimum number of acyclic subgraphs covering the vertex set of . A tournament is a hero if every -free tournament has chr…
Coloring tournaments: from local to global
Ararat Harutyunyan, Tien-Nam Le, Stéphan Thomassé +1
The \emph{chromatic number} of a directed graph is the minimum number of colors needed to color the vertices of such that each color class of induces an acyclic subdigr…
Exact distance coloring in trees
Nicolas Bousquet, Louis Esperet, Ararat Harutyunyan +1
For an integer and an even integer , consider the graph obtained from a large complete -ary tree by connecting with an edge any two vertices at distance exactly …
A Proof of the Barát-Thomassen Conjecture
Julien Bensmail, Ararat Harutyunyan, Tien-Nam Le +2
The Barát-Thomassen conjecture asserts that for every tree on edges, there exists a constant such that every -edge-connected graph with size divisible by can…
List coloring digraphs
Julien Bensmail, Ararat Harutyunyan, Ngoc Khang Le
The dichromatic number of a digraph is the least number such that the vertex set of can be partitioned into parts each of which induces an acyclic subdig…
Disjoint cycles of different lengths in graphs and digraphs
Julien Bensmail, Ararat Harutyunyan, Ngoc Khang Le +2
Understanding how the cycles of a graph or digraph behave in general has always been an important point of graph theory. In this paper, we study the question of finding a set of $k…
Disproving the normal graph conjecture
Ararat Harutyunyan, Lucas Pastor, Stéphan Thomassé
A graph is called normal if there exist two coverings, and of its vertex set such that every member of induces a clique in , every mem…
Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture
Julien Bensmail, Ararat Harutyunyan, Tien-Nam Le +1
The Barát-Thomassen conjecture asserts that there is a function such that for every fixed tree with edges, every graph which is -edge-connected with its number of…
Planar digraphs of digirth five are 2-colorable
Ararat Harutyunyan, Bojan Mohar
Neumann-Lara (1985) and Škrekovski conjectured that every planar digraph with digirth at least three is 2-colorable. We prove a relaxed version of this conjecture: every planar dig…
Planar graphs have exponentially many 3-arboricities
Ararat Harutyunyan, Bojan Mohar
It is well-known that every planar or projective planar graph can be 3-colored so that each color class induces a forest. This bound is sharp. In this paper, we show that there are…
Two results on the digraph chromatic number
Ararat Harutyunyan, Bojan Mohar
It is known (Bollobás (1978); Kostochka and Mazurova (1977)) that there exist graphs of maximum degree and of arbitrarily large girth whose chromatic number is at least $c Δ/ \…
Strengthened Brooks Theorem for digraphs of girth three
Ararat Harutyunyan, Bojan Mohar
Brooks' Theorem states that a connected graph of maximum degree has chromatic number at most , unless is an odd cycle or a complete graph. A result of Johansson (199…
Uniquely D-colourable digraphs with large girth
Ararat Harutyunyan, P. Mark Kayll, Bojan Mohar +1
Let C and D be digraphs. A mapping is a C-colouring if for every arc of D, either is an arc of C or , and the preimage of every vertex o…