Source author record

Ararat Harutyunyan

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Complexity Discrete Mathematics

Catalog footprint

Research overview

11works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Digraph Coloring and Distance to Acyclicity

In $k$ -Digraph Coloring we are given a digraph and are asked to partition its vertices into at most $k$ sets, so that each set induces a DAG. This well-known problem is NP-hard, as it generalizes (undirected) $k$ -Coloring, but becomes trivial if the input digraph is acyclic. This poses the natural parameterized complexity question what happens when the input is "almost" acyclic. In this paper we study this question using parameters that measure the input's distance to acyclicity in either the directed or the undirected sense. It is already known that, for all $k\ge 2$ , $k$ -Digraph Coloring is NP-hard on digraphs of DFVS at most $k+4$ . We strengthen this result to show that, for all $k\ge 2$ , $k$ -Digraph Coloring is NP-hard for DFVS $k$ . Refining our reduction we obtain two further consequences: (i) for all $k\ge 2$ , $k$ -Digraph Coloring is NP-hard for graphs of feedback arc set (FAS) at most $k^2$ ; interestingly, this leads to a dichotomy, as we show that the problem is FPT by $k$ if FAS is at most $k^2-1$ ; (ii) $k$ -Digraph Coloring is NP-hard for graphs of DFVS $k$ , even if the maximum degree $Δ$ is at most $4k-1$ ; we show that this is also almost tight, as the problem becomes FPT for DFVS $k$ and $Δ\le 4k-3$ . We then consider parameters that measure the distance from acyclicity of the underlying graph. We show that $k$ -Digraph Coloring admits an FPT algorithm parameterized by treewidth, whose parameter dependence is $(tw!)k^{tw}$ . Then, we pose the question of whether the $tw!$ factor can be eliminated. Our main contribution in this part is to settle this question in the negative and show that our algorithm is essentially optimal, even for the much more restricted parameter treedepth and for $k=2$ . Specifically, we show that an FPT algorithm solving $2$ -Digraph Coloring with dependence $td^{o(td)}$ would contradict the ETH.

preprint2020arXiv

Disproving the normal graph conjecture

A graph $G$ is called normal if there exist two coverings, $\mathbb{C}$ and $\mathbb{S}$ of its vertex set such that every member of $\mathbb{C}$ induces a clique in $G$ , every member of $\mathbb{S}$ induces an independent set in $G$ and $C \cap S \neq \emptyset$ for every $C \in \mathbb{C}$ and $S \in \mathbb{S}$ . It has been conjectured by De Simone and Körner in 1999 that a graph $G$ is normal if $G$ does not contain $C_5$ , $C_7$ and $\overline{C_7}$ as an induced subgraph. We disprove this conjecture.

preprint2016arXiv

A Proof of the Barát-Thomassen Conjecture

The Barát-Thomassen conjecture asserts that for every tree $T$ on $m$ edges, there exists a constant $k_T$ such that every $k_T$ -edge-connected graph with size divisible by $m$ can be edge-decomposed into copies of $T$ . So far this conjecture has only been verified when $T$ is a path or when $T$ has diameter at most 4. Here we prove the full statement of the conjecture.

preprint2016arXiv

Disjoint cycles of different lengths in graphs and digraphs

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$ vertex-disjoint cycles (resp. directed cycles) of distinct lengths in a given graph (resp. digraph). In the context of undirected graphs, we prove that, for every $k \geq 1$ , every graph with minimum degree at least $\frac{k^2+5k-2}{2}$ has $k$ vertex-disjoint cycles of different lengths, where the degree bound is best possible. We also consider stronger situations, and exhibit degree bounds (some of which are best possible) when e.g. the graph is triangle-free, or the $k$ cycles are requested to have different lengths congruent to some values modulo some $r$ . In the context of directed graphs, we consider a conjecture of Lichiardopol concerning the least minimum out-degree required for a digraph to have $k$ vertex-disjoint directed cycles of different lengths. We verify this conjecture for tournaments, and, by using the probabilistic method, for regular digraphs and digraphs of small order.

preprint2016arXiv

Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture

The Barát-Thomassen conjecture asserts that there is a function $f$ such that for every fixed tree $T$ with $t$ edges, every graph which is $f(t)$ -edge-connected with its number of edges divisible by $t$ has a partition of its edges into copies of $T$ . This has been proved in the case of paths of length $2^k$ by Thomassen, and recently shown to be true for all paths by Botler, Mota, Oshiro and Wakabayashi. Our goal in this paper is to propose an alternative proof of the path case with a weaker hypothesis: Namely, we prove that there is a function $f$ such that every $24$ -edge-connected graph with minimum degree $f(t)$ has an edge-partition into paths of length $t$ whenever $t$ divides the number of edges. We also show that $24$ can be dropped to $4$ when the graph is eulerian.

preprint2015arXiv

List coloring digraphs

The dichromatic number $\vecχ(D)$ of a digraph $D$ is the least number $k$ such that the vertex set of $D$ can be partitioned into $k$ parts each of which induces an acyclic subdigraph. Introduced by Neumann-Lara in 1982, this digraph invariant shares many properties with the usual chromatic number of graphs and can be seen as the natural analog of the graph chromatic number. In this paper, we study the list dichromatic number of digraphs, giving evidence that this notion generalizes the list chromatic number of graphs. We first prove that the list dichromatic number and the dichromatic number behave the same in many contexts, such as in small digraphs (by proving a directed version of Ohba's Conjecture), tournaments, and random digraphs. We then consider bipartite digraphs, and show that their list dichromatic number can be as large as $Ω(\log_2 n)$ . We finally give a Brooks-type upper bound on the list dichromatic number of digon-free digraphs.

preprint2014arXiv

Planar digraphs of digirth five are 2-colorable

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 digraph of digirth at least five is 2-colorable. The result also holds in the setting of list colorings.

preprint2014arXiv

Strong edge-colouring of sparse planar graphs

A strong edge-colouring of a graph is a proper edge-colouring where each colour class induces a matching. It is known that every planar graph with maximum degree $Δ$ has a strong edge-colouring with at most $4Δ+4$ colours. We show that $3Δ+1$ colours suffice if the graph has girth 6, and $4Δ$ colours suffice if $Δ\geq 7$ or the girth is at least 5. In the last part of the paper, we raise some questions related to a long-standing conjecture of Vizing on proper edge-colouring of planar graphs.

preprint2011arXiv

Planar graphs have exponentially many 3-arboricities

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 in fact exponentially many 3-colorings of this kind for any (projective) planar graph. The same result holds in the setting of 3-list-colorings.

preprint2011arXiv

Strengthened Brooks Theorem for digraphs of girth three

Brooks' Theorem states that a connected graph $G$ of maximum degree $Δ$ has chromatic number at most $Δ$ , unless $G$ is an odd cycle or a complete graph. A result of Johansson (1996) shows that if $G$ is triangle-free, then the chromatic number drops to $O(Δ/ \log Δ)$ . In this paper, we derive a weak analog for the chromatic number of digraphs. We show that every (loopless) digraph $D$ without directed cycles of length two has chromatic number $χ(D) \leq (1-e^{-13}) \tildeΔ$ , where $\tildeΔ$ is the maximum geometric mean of the out-degree and in-degree of a vertex in $D$ , when $\tildeΔ$ is sufficiently large. As a corollary it is proved that there exists an absolute constant $α< 1$ such that $χ(D) \leq α(\tildeΔ + 1)$ for every $\tildeΔ > 2$ .

preprint2011arXiv

Two results on the digraph chromatic number

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 Δ/ \log Δ$ . We show an analogous result for digraphs where the chromatic number of a digraph $D$ is defined as the minimum integer $k$ so that $V(D)$ can be partitioned into $k$ acyclic sets, and the girth is the length of the shortest cycle in the corresponding undirected graph. It is also shown, in the same vein as an old result of Erdos (1962), that there are digraphs with arbitrarily large chromatic number where every large subset of vertices is 2-colorable.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ararat Harutyunyan

Research overview

Is this your work?

11 publications

Digraph Coloring and Distance to Acyclicity

Disproving the normal graph conjecture

A Proof of the Barát-Thomassen Conjecture

Disjoint cycles of different lengths in graphs and digraphs

Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture

List coloring digraphs

Planar digraphs of digirth five are 2-colorable

Strong edge-colouring of sparse planar graphs

Planar graphs have exponentially many 3-arboricities

Strengthened Brooks Theorem for digraphs of girth three

Two results on the digraph chromatic number

See the researcher in context

Building this map preview