R. Naserasr

activity

20102026

most citedIdentification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity

43 citations · 237 across the 31 of their papers we have counts for

collaborators

Showing 2016Show all

3 papers · 1 filter

math.CO2016★ 9 cited

Homomorphism bounds and edge-colourings of $K_{4}$ -minor-free graphs

Laurent Beaudou, Florent Foucaud, Reza Naserasr

We present a necessary and sufficient condition for a graph of odd-girth $2 k + 1$ to bound the class of $K_{4}$ -minor-free graphs of odd-girth (at least) $2 k + 1$ , that is, to admit a ho…

math.CO2016

Smallest $C_{2 l + 1}$ -critical graphs of odd-girth $2 k + 1$

Laurent Beaudou, Florent Foucaud, Reza Naserasr

Given a graph $H$ , a graph $G$ is called $H$ -critical if $G$ does not admit a homomorphism to $H$ , but any proper subgraph of $G$ does. Observe that $K_{k - 1}$ -critical graphs are t…

cs.DS2016★ 11 cited

The complexity of tropical graph homomorphisms

Florent Foucaud, Ararat Harutyunyan, Pavol Hell +3

A tropical graph $(H, c)$ consists of a graph $H$ and a (not necessarily proper) vertex-colouring $c$ of $H$ . Given two tropical graphs $(G, c_{1})$ and $(H, c)$ , a homomorphism of $(G,…

Homomorphism bounds and edge-colourings of K4​-minor-free graphs

Smallest C2l+1​-critical graphs of odd-girth 2k+1

The complexity of tropical graph homomorphisms

Homomorphism bounds and edge-colourings of $K_{4}$ -minor-free graphs

Smallest $C_{2 l + 1}$ -critical graphs of odd-girth $2 k + 1$