Source author record

Soumen Nandi

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

ResearcherUnclaimed source record

Discrete Mathematics math.CO Computational Geometry

Catalog footprint

Research overview

6works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On clique numbers of colored mixed graphs

An (m,n)-colored mixed graph, or simply, an (m,n)-graph is a graph having m different types of arcs and n different types of edges. A homomorphism of an (m,n)-graph G to another (m,n)-graph H is a vertex mapping that preserves adjacency, the type thereto and the direction. A subset R of the set of vertices of G that always maps distinct vertices in itself to distinct image vertices under any homomorphism is called an (m,n)-relative clique of G. The maximum cardinality of an (m,n)-relative clique of a graph is called the (m,n)-relative clique number of the graph. In this article, we explore the (m,n)-relative clique numbers for various families of graphs.

preprint2022arXiv

The oriented relative clique number of triangle-free planar graphs is 10

In relation to oriented coloring and chromatic number, the parameter oriented relative clique number of an oriented graph $\overrightarrow{G}$ , denoted by $ω_{ro}(\overrightarrow{G})$ , is the main focus of this work. We solve an open problem mentioned in the recent survey on oriented coloring by Sopena (Discrete Mathematics 2016), and positively settle a conjecture due to Sen (PhD thesis 2014), by proving that the maximum value of $ω_{ro}(\overrightarrow{G})$ is $10$ when $\overrightarrow{G}$ is a planar graph.

preprint2016arXiv

Chromatic number of signed graphs with bounded maximum degree

A signed graph $(G, Σ)$ is a graph positive and negative ( $Σ$ denotes the set of negative edges). To re-sign a vertex $v$ of a signed graph $(G, Σ)$ is to switch the signs of the edges incident to $v$ . If one can obtain $(G, Σ')$ by re-signing some vertices of $(G, Σ)$ , then $(G, Σ) \equiv (G, Σ')$ . A signed graphs $(G, Σ)$ admits an homomorphism to $(H, Λ)$ if there is a sign preserving vertex mapping from $(G,Σ')$ to $(H, Λ)$ for some $(G, Σ) \equiv (G, Σ')$ . The signed chromatic number $χ_{s}( (G, Σ))$ of the signed graph $(G, Σ)$ is the minimum order (number of vertices) of a signed graph $(H, Λ)$ such that $(G, Σ)$ admits a homomorphism to $(H, Λ)$ . For a family $\mathcal{F}$ of signed graphs $χ_{s}(\mathcal{F}) = \text{max}_{(G,Σ) \in \mathcal{F}} χ_{s}( (G, Σ))$ . We prove $2^{Δ/2-1} \leq χ_s(\mathcal{G}_Δ) \leq (Δ-1)^2. 2^{(Δ-1)} +2$ for all $Δ\geq 3$ where $\mathcal{G}_Δ$ is the family of connected signed graphs with maximum degree $Δ$ . \end{abstract}

preprint2015arXiv

Approximation algorithms for the two-center problem of convex polygon

Given a convex polygon $P$ with $n$ vertices, the two-center problem is to find two congruent closed disks of minimum radius such that they completely cover $P$ . We propose an algorithm for this problem in the streaming setup, where the input stream is the vertices of the polygon in clockwise order. It produces a radius $r$ satisfying $r\leq2r_{opt}$ using $O(1)$ space, where $r_{opt}$ is the optimum solution. Next, we show that in non-streaming setup, we can improve the approximation factor by $r\leq 1.84 r_{opt}$ , maintaining the time complexity of the algorithm to $O(n)$ , and using $O(1)$ extra space in addition to the space required for storing the input.

preprint2015arXiv

On chromatic number of colored mixed graphs

An $(m,n)$ -colored mixed graph $G$ is a graph with its arcs having one of the $m$ different colors and edges having one of the $n$ different colors. A homomorphism $f$ of an $(m,n)$ -colored mixed graph $G$ to an $(m,n)$ -colored mixed graph $H$ is a vertex mapping such that if $uv$ is an arc (edge) of color $c$ in $G$ , then $f(u)f(v)$ is an arc (edge) of color $c$ in $H$ . The \textit{ $(m,n)$ -colored mixed chromatic number} $χ_{(m,n)}(G)$ of an $(m,n)$ -colored mixed graph $G$ is the order (number of vertices) of the smallest homomorphic image of $G$ . This notion was introduced by Nešetřil and Raspaud (2000, J. Combin. Theory, Ser. B 80, 147--155). They showed that $χ_{(m,n)}(G) \leq k(2m+n)^{k-1}$ where $G$ is a $k$ -acyclic colorable graph. We proved the tightness of this bound. We also showed that the acyclic chromatic number of a graph is bounded by $k^2 + k^{2 + \lceil log_{(2m+n)} log_{(2m+n)} k \rceil}$ if its $(m,n)$ -colored mixed chromatic number is at most $k$ . Furthermore, using probabilistic method, we showed that for graphs with maximum degree $Δ$ its $(m,n)$ -colored mixed chromatic number is at most $2(Δ-1)^{2m+n} (2m+n)^{Δ-1}$ . In particular, the last result directly improves the upper bound $2Δ^2 2^Δ$ of oriented chromatic number of graphs with maximum degree $Δ$ , obtained by Kostochka, Sopena and Zhu (1997, J. Graph Theory 24, 331--340) to $2(Δ-1)^2 2^{Δ-1}$ . We also show that there exists a graph with maximum degree $Δ$ and $(m,n)$ -colored mixed chromatic number at least $(2m+n)^{Δ/ 2}$ .

preprint2015arXiv

On oriented cliques with respect to push operation

To push a vertex $v$ of a directed graph $\overrightarrow{G}$ is to change the orientations of all the arcs incident with $v$ . An oriented graph is a directed graph without any cycle of length at most 2. An oriented clique is an oriented graph whose non-adjacent vertices are connected by a directed 2-path. A push clique is an oriented clique that remains an oriented clique even if one pushes any set of vertices of it. We show that it is NP-complete to decide if an undirected graph is underlying graph of a push clique or not. We also prove that a planar push clique can have at most 8 vertices. We also provide an exhaustive list of minimal (with respect to spanning subgraph inclusion) planar push cliques.

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.

Soumen Nandi

Research overview

Is this your work?

6 publications

On clique numbers of colored mixed graphs

The oriented relative clique number of triangle-free planar graphs is 10

Chromatic number of signed graphs with bounded maximum degree

Approximation algorithms for the two-center problem of convex polygon

On chromatic number of colored mixed graphs

On oriented cliques with respect to push operation

See the researcher in context

Building this map preview