L. Sunil Chandran
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
L. Sunil Chandran has a total of 82 co-authors. Here are the top co-authors by number of shared publications:
- Deepak Rajendraprasad
Indian Institute of Technology Palakkad Palakkad India
16 shared publications - Manu Basavaraju
Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India
10 shared publications - Mathew C. Francis
Indian Statistical Institute Chennai India
10 shared publications - Rogers Mathew
Department of Computer Science and Engineering Indian Institute of Technology Hyderabad
6 shared publications - Abhijin Adiga
Department of Computer Science and Automation Indian Institute of Science Bangalore-560012 India
5 shared publications - Davis Issac
Hasso Plattner Institute, Potsdam, Germany
5 shared publications
Latest Publications
- 13 October 2026
- Published by Wiley in Journal of Graph Theory
Vertex‐Based Localization of Erdős–Gallai Theorems for Paths and Cycles
For a simple graph , let and denote the number of vertices and edges in , respectively. The Erdős–Gallai theorem for paths states that in a simple ‐free graph, , where denotes a path with length (i.e., with edges). In this paper, we generalize this result as follows: For each , let be the length of the longest path that contains . We show that The Erdős–Gallai theorem for cycles states that in a simple graph with circumference (i.e., the length of the longest cycle) at most , we have . We strengthen this result as follows: For each , let be the length of the longest cycle that contains , or 2 if is not part of any cycle. We prove that where denotes the circumference of . Furthermore, we characterize the class of extremal graphs that attain equality in these bounds.
- 13 October 2026
- Published by Wiley in Journal of Graph Theory
Vertex‐Based Localization of Erdős–Gallai Theorems for Paths and Cycles
For a simple graph , let and denote the number of vertices and edges in , respectively. The Erdős–Gallai theorem for paths states that in a simple ‐free graph, , where denotes a path with length (i.e., with edges). In this paper, we generalize this result as follows: For each , let be the length of the longest path that contains . We show that The Erdős–Gallai theorem for cycles states that in a simple graph with circumference (i.e., the length of the longest cycle) at most , we have . We strengthen this result as follows: For each , let be the length of the longest cycle that contains , or 2 if is not part of any cycle. We prove that where denotes the circumference of . Furthermore, we characterize the class of extremal graphs that attain equality in these bounds.
- 23 March 2026
- Published by Wiley in Journal of Graph Theory
- Vol. 112 (3) , 235-254
χ‐Binding Functions for Squares of Convex Bipartite Graphs and Partite Testability for Bipartite Squares
A class of graphs is ‐bounded if there exists a function such that for each graph , where and are the chromatic and clique number of , respectively. The square of a graph , denoted as , is the graph with the same vertex set as in which two vertices are adjacent when they are at a distance at most two in . In this paper, we study the ‐boundedness of squares of bipartite graphs and its subclasses. Note that the class of squares of graphs, in general, admit a quadratic ‐binding function. Moreover, there exist bipartite graphs for which is . We first ask the following question: “What sub‐classes of bipartite graphs have a linear ‐binding function?” We focus on the class of convex bipartite graphs and prove the following result: for any convex bipartite graph , . Our proof also yields a polynomial‐time 3/2‐approximation algorithm for coloring squares of convex bipartite graphs. We then introduce a notion called “partite testable properties” for the squares of bipartite graphs. We say that a graph property is partite testable for the squares of bipartite graphs if for a bipartite graph , whenever the induced subgraphs and satisfies the property then also satisfies the property . Here, we discuss whether some of the well‐known graph properties like perfectness , chordality , (anti‐hole)‐freeness , and so on. are partite testable or not. As a consequence, we prove that the squares of biconvex bipartite graphs are perfect.
- 23 March 2026
- Published by Wiley in Journal of Graph Theory
- Vol. 112 (3) , 235-254
χ‐Binding Functions for Squares of Convex Bipartite Graphs and Partite Testability for Bipartite Squares
A class of graphs is ‐bounded if there exists a function such that for each graph , where and are the chromatic and clique number of , respectively. The square of a graph , denoted as , is the graph with the same vertex set as in which two vertices are adjacent when they are at a distance at most two in . In this paper, we study the ‐boundedness of squares of bipartite graphs and its subclasses. Note that the class of squares of graphs, in general, admit a quadratic ‐binding function. Moreover, there exist bipartite graphs for which is . We first ask the following question: “What sub‐classes of bipartite graphs have a linear ‐binding function?” We focus on the class of convex bipartite graphs and prove the following result: for any convex bipartite graph , . Our proof also yields a polynomial‐time 3/2‐approximation algorithm for coloring squares of convex bipartite graphs. We then introduce a notion called “partite testable properties” for the squares of bipartite graphs. We say that a graph property is partite testable for the squares of bipartite graphs if for a bipartite graph , whenever the induced subgraphs and satisfies the property then also satisfies the property . Here, we discuss whether some of the well‐known graph properties like perfectness , chordality , (anti‐hole)‐freeness , and so on. are partite testable or not. As a consequence, we prove that the squares of biconvex bipartite graphs are perfect.
- 13 February 2026
- Published by Springer Nature
- p. 1-15
Localization: A Framework to Generalize Extremal Graph Problems
- 13 February 2026
- Published by Springer Nature
- p. 1-15
Localization: A Framework to Generalize Extremal Graph Problems
- Open Access
- 9 December 2025
- Published by Association for Computing Machinery (ACM) in ACM Journal on Autonomous Transportation Systems
- Vol. 3 (2) , 1-17
Near-Linear Time Scheduling for Drone-Based Parcel Delivery from a Warehouse
We consider the problem where a warehouse has multiple drones and wants to deliver parcels to several customers. Each drone picks a parcel from the warehouse, delivers it and returns to the warehouse. The speeds and battery lives of the drones could be different and due to the limited battery life, each drone has a bounded range in which it can deliver parcels. The goal is to assign parcels to the drones so that the time taken to deliver all the parcels is minimized. This turns out to be an NP-hard problem, and hence, the focus of this article is to design a fast approximation algorithm. We do this by adapting the Longest Processing Time First (LPT) heuristic, which is a classical heuristic for the fundamental problem of uniform machine scheduling to the Drones Warehouse Problem (DWP) , which is a natural generalization of the uniform machine scheduling problem. We prove that the natural approach of solving this problem via the LPT heuristic has an approximation factor of ϕ, where ϕ ≈ 1.62 is the golden ratio. LPT heuristic was first considered by Gonzalez et al. (SIAM J. Comput. 6(1):155–166, 1977) . Since then, extensive work has been done to improve the approximation factor of the LPT heuristic. However, all known implementations of the LPT heuristic take O(mn) time, where m is the number of machines and n is the number of jobs. In this work, we come up with the first near-linear time implementation for LPT both for DWP and Uniform Scheduling. Specifically, the running time is O((n+m) (log 2 m +log n )). Somewhat surprisingly, the result is obtained by mapping the problem to dynamic maintenance of lower envelope lines, which has been well-studied in the computational geometry community.
- 9 December 2025
- Published by Association for Computing Machinery (ACM) in ACM Journal on Autonomous Transportation Systems
- Vol. 3 (2) , 1-17
Open AccessNear-Linear Time Scheduling for Drone-Based Parcel Delivery from a Warehouse
We consider the problem where a warehouse has multiple drones and wants to deliver parcels to several customers. Each drone picks a parcel from the warehouse, delivers it and returns to the warehouse. The speeds and battery lives of the drones could be different and due to the limited battery life, each drone has a bounded range in which it can deliver parcels. The goal is to assign parcels to the drones so that the time taken to deliver all the parcels is minimized. This turns out to be an NP-hard problem, and hence, the focus of this article is to design a fast approximation algorithm. We do this by adapting the Longest Processing Time First (LPT) heuristic, which is a classical heuristic for the fundamental problem of uniform machine scheduling to the Drones Warehouse Problem (DWP) , which is a natural generalization of the uniform machine scheduling problem. We prove that the natural approach of solving this problem via the LPT heuristic has an approximation factor of ϕ, where ϕ ≈ 1.62 is the golden ratio. LPT heuristic was first considered by Gonzalez et al. (SIAM J. Comput. 6(1):155–166, 1977) . Since then, extensive work has been done to improve the approximation factor of the LPT heuristic. However, all known implementations of the LPT heuristic take O(mn) time, where m is the number of machines and n is the number of jobs. In this work, we come up with the first near-linear time implementation for LPT both for DWP and Uniform Scheduling. Specifically, the running time is O((n+m) (log 2 m +log n )). Somewhat surprisingly, the result is obtained by mapping the problem to dynamic maintenance of lower envelope lines, which has been well-studied in the computational geometry community.
- Open Access
Generalized Zykov's Theorem
For a simple graph $G$, let $n$ denote its number of vertices, and let $N(G,K_t)$ denote the number of copies of $K_t$ in $G$. Zykov's theorem (1949) asserts that for any $K_{r+1}$-free graph and $t \ge 2$, \[ N(G,K_t) \le {r \choose t}\left(\frac{n}{r}\right)^t \] We generalize Zykov's bound within a vertex-based localization framework. For each vertex $v \in V(G)$, let $c(v)$ denote the order of the largest clique containing $v$. In this paper, we show that \[ N(G,K_t) \le n^{t-1} \sum_{v \in V(G)} \frac{1}{c(v)^t} {c(v) \choose t} \] We further show that equality holds if and only if $G$ is a regular complete multipartite graph. \newline Note that if we impose the condition that, $G$ is $K_{r+1}$-free, then $c(v) \leq r$ for all $v \in V(G)$. Thus, plugging $c(v) = r$ for all $v \in V(G)$, we retrieve Zykov's bound.Open AccessGeneralized Zykov's Theorem
For a simple graph $G$, let $n$ denote its number of vertices, and let $N(G,K_t)$ denote the number of copies of $K_t$ in $G$. Zykov's theorem (1949) asserts that for any $K_{r+1}$-free graph and $t \ge 2$, \[ N(G,K_t) \le {r \choose t}\left(\frac{n}{r}\right)^t \] We generalize Zykov's bound within a vertex-based localization framework. For each vertex $v \in V(G)$, let $c(v)$ denote the order of the largest clique containing $v$. In this paper, we show that \[ N(G,K_t) \le n^{t-1} \sum_{v \in V(G)} \frac{1}{c(v)^t} {c(v) \choose t} \] We further show that equality holds if and only if $G$ is a regular complete multipartite graph. \newline Note that if we impose the condition that, $G$ is $K_{r+1}$-free, then $c(v) \leq r$ for all $v \in V(G)$. Thus, plugging $c(v) = r$ for all $v \in V(G)$, we retrieve Zykov's bound. - 28 November 2025
- Published by Springer Nature in Indian Journal of Pure and Applied Mathematics
- Vol. 57 (1) , 4-38
A survey on the boxicity and cubicity of graphs
- 28 November 2025
- Published by Springer Nature in Indian Journal of Pure and Applied Mathematics
- Vol. 57 (1) , 4-38
A survey on the boxicity and cubicity of graphs
- Open AccessCNFs and DNFs with Exactly $k$ SolutionsModel counting is a fundamental problem that consists of determining the number of satisfying assignments for a given Boolean formula. The weighted variant, which computes the weighted sum of satisfying assignments, has extensive applications in probabilistic reasoning, network reliability, statistical physics, and formal verification. A common approach for solving weighted model counting is to reduce it to unweighted model counting, which raises an important question: {\em What is the minimum number of terms (or clauses) required to construct a DNF (or CNF) formula with exactly $k$ satisfying assignments?} In this paper, we establish both upper and lower bounds on this question. We prove that for any natural number $k$, one can construct a monotone DNF formula with exactly $k$ satisfying assignments using at most $O(\sqrt{\log k}\log\log k)$ terms. This construction represents the first $o(\log k)$ upper bound for this problem. We complement this result by showing that there exist infinitely many values of $k$ for which any DNF or CNF representation requires at least $Ω(\log\log k)$ terms or clauses. These results have significant implications for the efficiency of model counting algorithms based on formula transformations.Open AccessCNFs and DNFs with Exactly $k$ SolutionsModel counting is a fundamental problem that consists of determining the number of satisfying assignments for a given Boolean formula. The weighted variant, which computes the weighted sum of satisfying assignments, has extensive applications in probabilistic reasoning, network reliability, statistical physics, and formal verification. A common approach for solving weighted model counting is to reduce it to unweighted model counting, which raises an important question: {\em What is the minimum number of terms (or clauses) required to construct a DNF (or CNF) formula with exactly $k$ satisfying assignments?} In this paper, we establish both upper and lower bounds on this question. We prove that for any natural number $k$, one can construct a monotone DNF formula with exactly $k$ satisfying assignments using at most $O(\sqrt{\log k}\log\log k)$ terms. This construction represents the first $o(\log k)$ upper bound for this problem. We complement this result by showing that there exist infinitely many values of $k$ for which any DNF or CNF representation requires at least $Ω(\log\log k)$ terms or clauses. These results have significant implications for the efficiency of model counting algorithms based on formula transformations.
- Open Access
Boxicity of Zero Divisor Graphs
A $d$-dimensional box is the cartesian product $R_i\times\cdots\times R_d$ where each $R_i$ is a closed interval on the real line. The boxicity of a graph, denoted as $box(G)$, is the minimum integer $d\geq 0$ such that $G$ is the intersection graph of a collection of $d$-dimensional boxes. The study of graph classes associated with algebraic structures is a fascinating area where graph theory and algebra meet. A well-known class of graphs associated with rings is the class of zero divisor graphs introduced by Beck in 1988. Since then, this graph class has been studied extensively by several researchers. Denote by $Z(R)$ the set of zero divisors of a ring $R$. The zero divisor graph $Γ(R)$ for a ring $R$ is defined as the graph with the vertex set $V(Γ(R))=Z(R)$ and $E(Γ(R))=\{\{a_i,a_j\}:a_ia_j\in Z(R)\text{ and }a_ia_j=0 \}$. Let $N=Π_{i=1}^ap_i^{n_i}$ be the prime factorization of $N$. In Discrete Applied Mathematics 365 (2025), pp. 260-269, it was shown that $box(Γ(\mathbb{Z}_N))\leqΠ_{i=1}^a(n_i+1)-Π_{i=1}^a(\lfloor n_i/2\rfloor+1)-1$. In this paper we exactly determine the boxicity of $Γ(\mathbb{Z}_N)$: We show that when $N\equiv 2\pmod 4$ and $N$ is not divisible by $p^3$ for any prime divisor $p$, we have $box(Γ(\mathbb{Z}_N))=a-1$. Otherwise $box(Γ(\mathbb{Z}_N))=a$. Suppose $R$ is a non-zero commutative ring with identity that is also a reduced ring and let $k$ be the size of the set of minimal prime ideals of $R$. In the same paper, it was showed that $box(Γ(R))\leq 2^k-2$. We improve this result by showing $\lfloor k/2\rfloor\leq box(Γ(R))\leq k$ with the same assumption on $R$. In this paper we also show that $a-1\leq\dim_{TH}(Γ(\mathbb{Z}_N))\leq a$ and $\lfloor k/2\rfloor\leq\dim_{TH}(Γ(R))\leq k$, where $\dim_{TH}$ is another dimensional parameter associated with graphs known as the threshold dimension.Open AccessBoxicity of Zero Divisor Graphs
A $d$-dimensional box is the cartesian product $R_i\times\cdots\times R_d$ where each $R_i$ is a closed interval on the real line. The boxicity of a graph, denoted as $box(G)$, is the minimum integer $d\geq 0$ such that $G$ is the intersection graph of a collection of $d$-dimensional boxes. The study of graph classes associated with algebraic structures is a fascinating area where graph theory and algebra meet. A well-known class of graphs associated with rings is the class of zero divisor graphs introduced by Beck in 1988. Since then, this graph class has been studied extensively by several researchers. Denote by $Z(R)$ the set of zero divisors of a ring $R$. The zero divisor graph $Γ(R)$ for a ring $R$ is defined as the graph with the vertex set $V(Γ(R))=Z(R)$ and $E(Γ(R))=\{\{a_i,a_j\}:a_ia_j\in Z(R)\text{ and }a_ia_j=0 \}$. Let $N=Π_{i=1}^ap_i^{n_i}$ be the prime factorization of $N$. In Discrete Applied Mathematics 365 (2025), pp. 260-269, it was shown that $box(Γ(\mathbb{Z}_N))\leqΠ_{i=1}^a(n_i+1)-Π_{i=1}^a(\lfloor n_i/2\rfloor+1)-1$. In this paper we exactly determine the boxicity of $Γ(\mathbb{Z}_N)$: We show that when $N\equiv 2\pmod 4$ and $N$ is not divisible by $p^3$ for any prime divisor $p$, we have $box(Γ(\mathbb{Z}_N))=a-1$. Otherwise $box(Γ(\mathbb{Z}_N))=a$. Suppose $R$ is a non-zero commutative ring with identity that is also a reduced ring and let $k$ be the size of the set of minimal prime ideals of $R$. In the same paper, it was showed that $box(Γ(R))\leq 2^k-2$. We improve this result by showing $\lfloor k/2\rfloor\leq box(Γ(R))\leq k$ with the same assumption on $R$. In this paper we also show that $a-1\leq\dim_{TH}(Γ(\mathbb{Z}_N))\leq a$ and $\lfloor k/2\rfloor\leq\dim_{TH}(Γ(R))\leq k$, where $\dim_{TH}$ is another dimensional parameter associated with graphs known as the threshold dimension. - Open Access
- 6 May 2025
- Published by Springer Nature in Bulletin of the Malaysian Mathematical Sciences Society
- Vol. 48 (4) , 1-15
Algorithms and Bounds for Very Strong Rainbow Coloring
A well-studied coloring problem is to assign colors to the edges of a graph G so that, for every pair of vertices, all edges of at least one shortest path between them receive different colors. The minimum number of colors necessary in such a coloring is the strong rainbow connection number ( $$\textbf{src}(G)$$ ) of the graph. When proving upper bounds on $$\textbf{src}(G)$$ , it is natural to prove that a coloring exists where, for every shortest path between every pair of vertices in the graph, all edges of the path receive different colors. Therefore, we introduce and formally define this more restricted edge coloring number, which we call very strong rainbow connection number ( $$\textbf{vsrc}(G)$$ ). In this paper, we give upper bounds on $$\textbf{vsrc}(G)$$ for several graph classes, some of which are tight. These immediately imply new upper bounds on $$\textbf{src}(G)$$ for these classes, showing that the study of $$\textbf{vsrc}(G)$$ enables meaningful progress on bounding $$\textbf{src}(G)$$ . Then we study the complexity of the problem to compute $$\textbf{vsrc}(G)$$ , particularly for graphs of bounded treewidth, and show this is an interesting problem in its own right. We prove that $$\textbf{vsrc}(G)$$ can be computed in polynomial time on cactus graphs; in contrast, this question is still open for $$\textbf{src}(G)$$ . We also observe that deciding whether $$\textbf{vsrc}(G) = k$$ is fixed-parameter tractable in k and the treewidth of G. Finally, on general graphs, we prove that there is no polynomial-time algorithm to decide whether $$\textbf{vsrc}(G) \le 3$$ nor to approximate $$\textbf{vsrc}(G)$$ within a factor $$n^{1-\varepsilon }$$ , unless P $$=$$ NP.- 6 May 2025
- Published by Springer Nature in Bulletin of the Malaysian Mathematical Sciences Society
- Vol. 48 (4) , 1-15
Open AccessAlgorithms and Bounds for Very Strong Rainbow Coloring
A well-studied coloring problem is to assign colors to the edges of a graph G so that, for every pair of vertices, all edges of at least one shortest path between them receive different colors. The minimum number of colors necessary in such a coloring is the strong rainbow connection number ( $$\textbf{src}(G)$$ ) of the graph. When proving upper bounds on $$\textbf{src}(G)$$ , it is natural to prove that a coloring exists where, for every shortest path between every pair of vertices in the graph, all edges of the path receive different colors. Therefore, we introduce and formally define this more restricted edge coloring number, which we call very strong rainbow connection number ( $$\textbf{vsrc}(G)$$ ). In this paper, we give upper bounds on $$\textbf{vsrc}(G)$$ for several graph classes, some of which are tight. These immediately imply new upper bounds on $$\textbf{src}(G)$$ for these classes, showing that the study of $$\textbf{vsrc}(G)$$ enables meaningful progress on bounding $$\textbf{src}(G)$$ . Then we study the complexity of the problem to compute $$\textbf{vsrc}(G)$$ , particularly for graphs of bounded treewidth, and show this is an interesting problem in its own right. We prove that $$\textbf{vsrc}(G)$$ can be computed in polynomial time on cactus graphs; in contrast, this question is still open for $$\textbf{src}(G)$$ . We also observe that deciding whether $$\textbf{vsrc}(G) = k$$ is fixed-parameter tractable in k and the treewidth of G. Finally, on general graphs, we prove that there is no polynomial-time algorithm to decide whether $$\textbf{vsrc}(G) \le 3$$ nor to approximate $$\textbf{vsrc}(G)$$ within a factor $$n^{1-\varepsilon }$$ , unless P $$=$$ NP. - 10 September 2024
- Published by Wiley in Journal of Graph Theory
- Vol. 108 (1) , 136-161
Variants of the Gyárfás–Sumner conjecture: Oriented trees and rainbow paths
Given a finite family of graphs, we say that a graph is “‐free” if does not contain any graph in as a subgraph. We abbreviate ‐free to just “‐free” when . A vertex‐colored graph is called “rainbow” if no two vertices of have the same color. Given an integer and a finite family of graphs , let denote the smallest integer such that any properly vertex‐colored ‐free graph having contains an induced rainbow path on vertices. Scott and Seymour showed that exists for every complete graph . A conjecture of N. R. Aravind states that . The upper bound on that can be obtained using the methods of Scott and Seymour setting are, however, super‐exponential. Gyárfás and Sárközy showed that . For , we show that and therefore, . This significantly improves Gyárfás and Sárközy's bound and also covers a bigger class of graphs. We adapt our proof to achieve much stronger upper bounds for graphs of higher girth: we prove that , where . Moreover, in each case, our results imply the existence of at least distinct induced rainbow paths on vertices. Along the way, we obtain some new results on an oriented variant of the Gyárfás–Sumner conjecture. For , let denote the orientations of in which one vertex has out‐degree or in‐degree . We show that every ‐free oriented graph having a chromatic number at least and every bikernel‐perfect oriented graph with girth having a chromatic number at least contains every oriented tree on at most vertices as an induced subgraph.
- 10 September 2024
- Published by Wiley in Journal of Graph Theory
- Vol. 108 (1) , 136-161
Variants of the Gyárfás–Sumner conjecture: Oriented trees and rainbow paths
Given a finite family of graphs, we say that a graph is “‐free” if does not contain any graph in as a subgraph. We abbreviate ‐free to just “‐free” when . A vertex‐colored graph is called “rainbow” if no two vertices of have the same color. Given an integer and a finite family of graphs , let denote the smallest integer such that any properly vertex‐colored ‐free graph having contains an induced rainbow path on vertices. Scott and Seymour showed that exists for every complete graph . A conjecture of N. R. Aravind states that . The upper bound on that can be obtained using the methods of Scott and Seymour setting are, however, super‐exponential. Gyárfás and Sárközy showed that . For , we show that and therefore, . This significantly improves Gyárfás and Sárközy's bound and also covers a bigger class of graphs. We adapt our proof to achieve much stronger upper bounds for graphs of higher girth: we prove that , where . Moreover, in each case, our results imply the existence of at least distinct induced rainbow paths on vertices. Along the way, we obtain some new results on an oriented variant of the Gyárfás–Sumner conjecture. For , let denote the orientations of in which one vertex has out‐degree or in‐degree . We show that every ‐free oriented graph having a chromatic number at least and every bikernel‐perfect oriented graph with girth having a chromatic number at least contains every oriented tree on at most vertices as an induced subgraph.