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

37 papers

math.CO2026

Winding number and circular coloring

Reza Naserasr, Cyril Pujol, Lujia Wang

In 1996, Youngs proved a surprising theorem that quadrangulations of the projective plane could never have chromatic number exactly 3. This sparked a lot of interest, and the resul…

math.CO2025

Extension of the Gyárfás-Sumner conjecture to signed graphs

Guillaume Aubian, Allen Ibiapina, Luis Kuffner +4

The balanced chromatic number of a signed graph G is the minimum number of balanced sets that cover all vertices of G. Studying structural conditions which imply bounds on the bala…

math.CO2025

Brooks' theorem for signed graphs with $Δ = 3$

Reza Naserasr, Huan Zhou

Circular $r$ -coloring of a signed graph $(G, σ)$ is a mapping of its vertices to a circle of circumference $r$ such that: I. each pair of vertices with a negative connection is at d…

math.CO2025

Fractional balanced chromatic number and arboricity of planar (signed) graphs

Reza Naserasr, Lan Anh Pham, Cyril Pujol +1

A fractional coloring of a signed graph $(G, σ)$ is an assignment of nonnegative weights to the balanced sets (sets which do not induce a negative cycle) such that each vertex has…

math.CO2025

On core of categorical product of (di)graphs

Reza Naserasr, Cyril Pujol

The core of a graph is the smallest graph (in terms of number of vertices) to which it is homomorphically equivalent. The question of the possible order of the core of the tensor p…

math.CO2025

Fractional balanced chromatic number of signed subcubic graphs

Xiaolan Hu, Luis Kuffner, Jiaao Li +4

A signed graph is a pair $(G, σ)$ , where $G$ is a graph and $σ : E (G) \to {-, +}$ , called signature, is an assignment of signs to the edges. Given a signed graph $(G, σ)$ wit…

math.CO2024

Colouring signed analogues of Kneser, Schrijver, and Borsuk graphs

Luis Kuffner, Reza Naserasr, Lujia Wang +3

The Kneser signed graph $\KS(n,k)$, $k \leq n$ , is the graph whose vertices are signed $k$ -subsets of $[n]$ (i.e. $k$ -subsets $S$ of ${\pm 1, \pm 2, \dots, \pm n}$ such that $S\…

math.CO2023

Balanced-chromatic number and Hadwiger-like conjectures

Andrea Jiménez, Jessica McDonald, Reza Naserasr +2

Motivated by different characterizations of planar graphs and the 4-Color Theorem, several structural results concerning graphs of high chromatic number have been obtained. Toward…

math.CO2023

Winding number and circular 4-coloring of signed graphs

Anna Gujgiczer, Reza Naserasr, Rohini S +1

Concerning the recent notion of circular chromatic number of signed graphs, for each given integer $k$ we introduce two signed bipartite graphs, each on $2 k^{2} - k + 1$ vertices, having…

math.CO2023

Critically 3-frustrated signed graphs

Chiara Cappello, Reza Naserasr, Eckhard Steffen +1

Extending the notion of maxcut, the study of the frustration index of signed graphs is one of the basic questions in the theory of signed graphs. Recently two of the authors initia…

math.CO2022★ 1 cited

Circular flows in mono-directed signed graphs

Jiaao Li, Reza Naserasr, Zhouningxin Wang +1

In this paper the concept of circular $r$ -flows in a mono-directed signed graph $(G, σ)$ is introduced. That is a pair $(D, f)$ , where $D$ is an orientation on $G$ and $f: E(G)\to…

math.CO2022★ 3 cited

Characterizing and recognizing exact-distance squares of graphs

Yandong Bai, Pedro P. Cortés, Reza Naserasr +1

For a graph $G = (V, E)$ , its exact-distance square, $G^{[♯2]}$ , is the graph with vertex set $V$ and with an edge between vertices $x$ and $y$ if and only if $x$ and $y$ have d…

math.CO2021

Extended Double Covers and Homomorphism Bounds of Signed Graphs

Florent Foucaud, Reza Naserasr, Rongxing Xu

A \emph{signed graph} $(G, σ)$ is a graph $G$ together with an assignment $σ : E (G) \to {+, -}$ . The notion of homomorphisms of signed graphs is a relatively new development…

math.CO2021

Signed bipartite circular cliques and a bipartite analogue of Grötzsch's theorem

Reza Naserasr, Zhouningxin Wang

The notion of the circular coloring of signed graphs is a recent one that simultaneously extends both notions of the circular coloring of graphs and $0$ -free coloring of signed gra…

math.CO2021★ 1 cited

Circular $(4 - ε)$ -coloring of some classes of signed graphs

František Kardoš, Jonathan Narboni, Reza Naserasr +1

A circular $r$ -coloring of a signed graph $(G, σ)$ is an assignment $ϕ$ of points of a circle $C_{r}$ of circumference $r$ to the vertices of $(G, σ)$ such that for each positive edg…

math.CO2021★ 3 cited

Mapping sparse signed graphs to $(K_{2 k}, M)$

Reza Naserasr, Riste Škrekovski, Zhouningxin Wang +1

A homomorphism of a signed graph $(G, σ)$ to $(H, π)$ is a mapping of vertices and edges of $G$ to (respectively) vertices and edges of $H$ such that adjacencies, incidences and th…

math.CO2021

Density of $C_{- 4}$ -critical signed graphs

Reza Naserasr, Lan Anh Pham, Zhouningxin Wang

A signed bipartite (simple) graph $(G, σ)$ is said to be $C_{- 4}$ -critical if it admits no homomorphism to $C_{- 4}$ (a negative 4-cycle) but every proper subgraph of it does. In th…

math.CO2020★ 1 cited

Circular chromatic number of signed graphs

Reza Naserasr, Zhouningxin Wang, Xuding Zhu

A signed graph is a pair $(G, σ)$ , where $G$ is a graph and $σ : E (G) \to {+, -}$ is a signature which assigns to each edge of $G$ a sign. Various notions of coloring of signed gr…

math.CO2020

Extension of Gyarfas-Sumner conjecture to digraphs

Pierre Aboulker, Pierre Charbit, Reza Naserasr

The dichromatic number of a digraph $D$ is the minimum number of colors needed to color its vertices in such a way that each color class induces an acyclic digraph. As it generaliz…

cs.DM2020★ 11 cited

Exact square coloring of subcubic planar graphs

Florent Foucaud, Hervé Hocquard, Suchismita Mishra +4

We study the exact square chromatic number of subcubic planar graphs. An exact square coloring of a graph G is a vertex-coloring in which any two vertices at distance exactly 2 rec…

math.CO2019

Homomorphisms of signed graphs: An update

Reza Naserasr, Eric Sopena, Thomas Zaslavsky

A signed graph is a graph together with an assignment of signs to the edges. A closed walk in a signed graph is said to be positive (negative) if it has an even (odd) number of neg…

math.CO2019

On the Structure of Small Strength- $2$ Covering Arrays

Janne I. Kokkala, Karen Meagher, Reza Naserasr +3

A covering array $CA (N; t, k, v)$ of strength $t$ is an $N \times k$ array of symbols from an alphabet of size $v$ such that in every $N \times t$ subarray, every $t$ -tuple occur…

math.CO2018★ 3 cited

Homomorphism bounds of signed bipartite $K_{4}$ -minor-free graphs and edge-colorings of $2 k$ -regular $K_{4}$ -minor-free multigraphs

Laurent Beaudou, Florent Foucaud, Reza Naserasr

A signed graph $(G, Σ)$ is a graph $G$ and a subset $Σ$ of its edges which corresponds to an assignment of signs to the edges: edges in $Σ$ are negative while edges not in $Σ$ are…

cs.DS2017

A New Graph Parameter To Measure Linearity

Pierre Charbit, Michel Habib, Lalla Mouatadid +1

Consider a sequence of LexBFS vertex orderings σ1, σ2, . . . where each ordering σi is used to break ties for σi+1. Since the total number of vertex orderings of a finite graph is…

Winding number and circular coloring

Extension of the Gyárfás-Sumner conjecture to signed graphs

Brooks' theorem for signed graphs with Δ=3

Fractional balanced chromatic number and arboricity of planar (signed) graphs

On core of categorical product of (di)graphs

Fractional balanced chromatic number of signed subcubic graphs

Colouring signed analogues of Kneser, Schrijver, and Borsuk graphs

Balanced-chromatic number and Hadwiger-like conjectures

Winding number and circular 4-coloring of signed graphs

Critically 3-frustrated signed graphs

Circular flows in mono-directed signed graphs

Characterizing and recognizing exact-distance squares of graphs

Extended Double Covers and Homomorphism Bounds of Signed Graphs

Signed bipartite circular cliques and a bipartite analogue of Grötzsch's theorem

Circular (4−ε)-coloring of some classes of signed graphs

Mapping sparse signed graphs to (K2k​,M)

Density of C−4​-critical signed graphs

Circular chromatic number of signed graphs

Extension of Gyarfas-Sumner conjecture to digraphs

Exact square coloring of subcubic planar graphs

Homomorphisms of signed graphs: An update

On the Structure of Small Strength-2 Covering Arrays

Homomorphism bounds of signed bipartite K4​-minor-free graphs and edge-colorings of 2k-regular K4​-minor-free multigraphs

A New Graph Parameter To Measure Linearity

Brooks' theorem for signed graphs with $Δ = 3$

Circular $(4 - ε)$ -coloring of some classes of signed graphs

Mapping sparse signed graphs to $(K_{2 k}, M)$

Density of $C_{- 4}$ -critical signed graphs

On the Structure of Small Strength- $2$ Covering Arrays

Homomorphism bounds of signed bipartite $K_{4}$ -minor-free graphs and edge-colorings of $2 k$ -regular $K_{4}$ -minor-free multigraphs