Source author record

Sagnik Sen

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 Data Structures and Algorithms

Catalog footprint

Research overview

13works

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.

preprint2021arXiv

On subgraph complementation to H-free graphs

For a class $\mathcal{G}$ of graphs, the problem SUBGRAPH COMPLEMENT TO $\mathcal{G}$ asks whether one can find a subset $S$ of vertices of the input graph $G$ such that complementing the subgraph induced by $S$ in $G$ results in a graph in $\mathcal{G}$ . We investigate the complexity of the problem when $\mathcal{G}$ is $H$ -free for $H$ being a complete graph, a star, a path, or a cycle. We obtain the following results: - When $H$ is a $K_t$ (a complete graph on $t$ vertices) for any fixed $t\geq 1$ , the problem is solvable in polynomial-time. This applies even when $\mathcal{G}$ is a subclass of $K_t$ -free graphs recognizable in polynomial-time, for example, the class of $(t-2)$ -degenerate graphs. - When $H$ is a $K_{1,t}$ (a star graph on $t+1$ vertices), we obtain that the problem is NP-complete for every $t\geq 5$ . This, along with known results, leaves only two unresolved cases - $K_{1,3}$ and $K_{1,4}$ . - When $H$ is a $P_t$ (a path on $t$ vertices), we obtain that the problem is NP-complete for every $t\geq 7$ , leaving behind only two unresolved cases - $P_5$ and $P_6$ . - When $H$ is a $C_t$ (a cycle on $t$ vertices), we obtain that the problem is NP-complete for every $t\geq 8$ , leaving behind four unresolved cases - $C_4, C_5, C_6,$ and $C_7$ . Further, we prove that these hard problems do not admit subexponential-time algorithms (algorithms running in time $2^{o(|V(G)|)}$ ), assuming the Exponential Time Hypothesis. A simple complementation argument implies that results for $\mathcal{G}$ are applicable for $\overline{\mathcal{G}}$ , thereby obtaining similar results for $H$ being the complement of a complete graph, a star, a path, or a cycle. Our results generalize two main results and resolve one open question by Fomin et al. (Algorithmica, 2020).

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}

preprint2016arXiv

On a special class of boxicity 2 graphs

We define and study a class of graphs, called 2-stab interval graphs (2SIG), with boxicity 2 which properly contains the class of interval graphs. A 2SIG is an axes-parallel rectangle intersection graph where the rectangles have unit height (that is, length of the side parallel to $Y$ -axis) and intersects either of the two fixed lines, parallel to the $X$ -axis, distance $1+ε$ ( $0 < ε< 1$ ) apart. Intuitively, 2SIG is a graph obtained by putting some edges between two interval graphs in a particular rule. It turns out that for these kind of graphs, the chromatic number of any of its induced subgraphs is bounded by twice of its (induced subgraph) clique number. This shows that the graph, even though not perfect, is not very far from it. Then we prove similar results for some subclasses of 2SIG and provide efficient algorithm for finding their clique number. We provide a matrix characterization for a subclass of 2SIG graph.

preprint2016arXiv

On local structures of cubicity 2 graphs

A 2-stab unit interval graph (2SUIG) is an axes-parallel unit square intersection graph where the unit squares intersect either of the two fixed lines parallel to the $X$ -axis, distance $1 + ε$ ( $0 < ε< 1$ ) apart. This family of graphs allow us to study local structures of unit square intersection graphs, that is, graphs with cubicity 2. The complexity of determining whether a tree has cubicity 2 is unknown while the graph recognition problem for unit square intersection graph is known to be NP-hard. We present a polynomial time algorithm for recognizing trees that admit a 2SUIG representation.

preprint2015arXiv

Analogous to cliques for (m,n)-colored mixed graphs

Vertex coloring of a graph $G$ with $n$ -colors can be equivalently thought to be a graph homomorphism (edge preserving vertex mapping) of $G$ to the complete graph $K_n$ of order $n$ . So, in that sense, the chromatic number $χ(G)$ of $G$ will be the order of the smallest complete graph to which $G$ admits a homomorphism to. As every graph, which is not a complete graph, admits a homomorphism to a smaller complete graph, we can redefine the chromatic number $χ(G)$ of $G$ to be the order of the smallest graph to which $G$ admits a homomorphism to. Of course, such a smallest graph must be a complete graph as they are the only graphs with chromatic number equal to their order. The concept of vertex coloring can be generalize for other types of graphs. Naturally, the chromatic number is defined to be the order of the smallest graph (of the same type) to which a graph admits homomorphism to. The analogous notion of clique turns out to be the graphs with order equal to their (so defined) "chromatic number". These "cliques" turns out to be much more complicated than their undirected counterpart and are interesting objects of study. In this article, we mainly study different aspects of "cliques" for signed (graphs with positive or negative signs assigned to each edge) and switchable signed graphs (equivalence class of signed graph with respect to switching signs of edges incident to the same vertex).

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 homomorphism of oriented graphs with respect to push operation

An oriented graph is a directed graph without any cycle of length at most 2. To push a vertex of a directed graph is to reverse the orientation of the arcs incident to that vertex. Klostermeyer and MacGillivray defined push graphs which are equivalence class of oriented graphs with respect to vertex pushing operation. They studied the homomorphism of the equivalence classes of oriented graphs with respect to push operation. In this article, we further study the same topic and answer some of the questions asked in the above mentioned work. The anti-twinned graph of an oriented graph is obtained by adding and pushing a copy of each of its vertices. In particular, we show that two oriented graphs are in a push relation if and only if they have isomorphic anti-twinned graphs. Moreover, we study oriented homomorphisms of outerplanar graphs with girth at least five, planar graphs and planar graphs with girth at least eight with respect to the push operation.

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.

preprint2015arXiv

Walk-powers and homomorphism bound of planar graphs

As an extension of the Four-Color Theorem it is conjectured that every planar graph of odd-girth at least $2k+1$ admits a homomorphism to $PC_{2k}=(\mathbb{Z}_2^{2k}, \{e_1, e_2, ...,e_{2k}, J\})$ where $e_i$ 's are standard basis and $J$ is all 1 vector. Noting that $PC_{2k}$ itself is of odd-girth $2k+1$ , in this work we show that if the conjecture is true, then $PC_{2k}$ is an optimal such a graph both with respect to number of vertices and number of edges. The result is obtained using the notion of walk-power of graphs and their clique numbers. An analogous result is proved for bipartite signed planar graphs of unbalanced-girth $2k$ . The work is presented on a uniform frame work of planar consistent signed graphs.

preprint2014arXiv

Homomorphisms of signed planar graphs

Signed graphs are studied since the middle of the last century. Recently, the notion of homomorphism of signed graphs has been introduced since this notion captures a number of well known conjectures which can be reformulated using the definitions of signed homomorphism. In this paper, we introduce and study the properties of some target graphs for signed homomorphism. Using these properties, we obtain upper bounds on the signed chromatic numbers of graphs with bounded acyclic chromatic number and of signed planar graphs with given girth.

preprint2014arXiv

Outerplanar and planar oriented cliques

The clique number of an undirected graph $G$ is the maximum order of a complete subgraph of $G$ and is a well-known lower bound for the chromatic number of $G$ . Every proper $k$ -coloring of $G$ may be viewed as a homomorphism (an edge-preserving vertex mapping) of $G$ to the complete graph of order $k$ . By considering homomorphisms of oriented graphs (digraphs without cycles of length at most 2), we get a natural notion of (oriented) colorings and oriented chromatic number of oriented graphs. An oriented clique is then an oriented graph whose number of vertices and oriented chromatic number coincide. However, the structure of oriented cliques is much less understood than in the undirected case. In this paper, we study the structure of outerplanar and planar oriented cliques. We first provide a list of 11 graphs and prove that an outerplanar graph can be oriented as an oriented clique if and only if it contains one of these graphs as a spanning subgraph. Klostermeyer and MacGillivray conjectured that the order of a planar oriented clique is at most 15, which was later proved by Sen [S. Sen. Maximum Order of a Planar Oclique Is 15. Proc. IWOCA'2012. {\em Lecture Notes Comput. Sci.} 7643:130--142]. We show that any planar oriented clique on 15 vertices must contain a particular oriented graph as a spanning subgraph, thus reproving the above conjecture. We also provide tight upper bounds for the order of planar oriented cliques of girth $k$ for all $k \ge 4$ .

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.

Sagnik Sen

Research overview

Is this your work?

13 publications

On clique numbers of colored mixed graphs

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

On subgraph complementation to H-free graphs

Chromatic number of signed graphs with bounded maximum degree

On a special class of boxicity 2 graphs

On local structures of cubicity 2 graphs

Analogous to cliques for (m,n)-colored mixed graphs

On chromatic number of colored mixed graphs

On homomorphism of oriented graphs with respect to push operation

On oriented cliques with respect to push operation

Walk-powers and homomorphism bound of planar graphs

Homomorphisms of signed planar graphs

Outerplanar and planar oriented cliques

See the researcher in context

Building this map preview