Faculty Publications

Now showing 1 - 4 of 4

Separation Dimension of Graphs and Hypergraphs
(Springer New York LLC barbara.b.bertram@gsk.com, 2016) Basavaraju, M.; Sunil Chandran, L.S.; Golumbic, M.C.; Mathew, R.; Rajendraprasad, D.
Separation dimension of a hypergraph H, denoted by ?( H) , is the smallest natural number k so that the vertices of H can be embedded in Rk such that any two disjoint edges of H can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph H is equal to the boxicity of the line graph of H. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension. In this paper, we study the separation dimension of hypergraphs and graphs. © 2015, Springer Science+Business Media New York.
Separation dimension and sparsity
(Wiley-Liss Inc. info@wiley.com, 2018) Alon, N.; Basavaraju, M.; Sunil Chandran, L.S.; Mathew, R.; Rajendraprasad, D.
The separation dimension ???(G) of a hypergraph G is the smallest natural number k for which the vertices of G can be embedded in Rk so that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the cardinality of a smallest family F of total orders of V(G), such that for any two disjoint edges of G, there exists at least one total order in F in which all the vertices in one edge precede those in the other. Separation dimension is a monotone parameter; adding more edges cannot reduce the separation dimension of a hypergraph. In this article, we discuss the influence of separation dimension and edge-density of a graph on one another. On one hand, we show that the maximum separation dimension of a k-degenerate graph on n vertices is O(k lg lg n) and that there exists a family of 2-degenerate graphs with separation dimension ?(lg lg n). On the other hand, we show that graphs with bounded separation dimension cannot be very dense. Quantitatively, we prove that n-vertex graphs with separation dimension s have at most 3(4 lg n)s?2 edges. We do not believe that this bound is optimal and give a question and a remark on the optimal bound. © 2018 Wiley Periodicals, Inc.
On induced colourful paths in triangle-free graphs
(Elsevier B.V., 2019) Babu, J.; Basavaraju, M.; Sunil Chandran, L.S.; Francis, M.C.
Given a graph G=(V,E) whose vertices have been properly coloured, we say that a path in G is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai–Roy–Vitaver Theorem that every properly coloured graph contains a colourful path on ?(G) vertices. We explore a conjecture that states that every properly coloured triangle-free graph G contains an induced colourful path on ?(G) vertices and prove its correctness when the girth of G is at least ?(G). Recent work on this conjecture by Gyárfás and Sárközy, and Scott and Seymour has shown the existence of a function f such that if ?(G)?f(k), then an induced colourful path on k vertices is guaranteed to exist in any properly coloured triangle-free graph G. © 2018 Elsevier B.V.
Variants of the Gyárfás–Sumner conjecture: Oriented trees and rainbow paths
(John Wiley and Sons Inc, 2025) Basavaraju, M.; Sunil Chandran, L.S.; Francis, M.C.; Murali, K.
Given a finite family (Formula presented.) of graphs, we say that a graph (Formula presented.) is “ (Formula presented.) -free” if (Formula presented.) does not contain any graph in (Formula presented.) as a subgraph. We abbreviate (Formula presented.) -free to just “ (Formula presented.) -free” when (Formula presented.). A vertex-colored graph (Formula presented.) is called “rainbow” if no two vertices of (Formula presented.) have the same color. Given an integer (Formula presented.) and a finite family of graphs (Formula presented.), let (Formula presented.) denote the smallest integer such that any properly vertex-colored (Formula presented.) -free graph (Formula presented.) having (Formula presented.) contains an induced rainbow path on (Formula presented.) vertices. Scott and Seymour showed that (Formula presented.) exists for every complete graph (Formula presented.). A conjecture of N. R. Aravind states that (Formula presented.). The upper bound on (Formula presented.) that can be obtained using the methods of Scott and Seymour setting (Formula presented.) are, however, super-exponential. Gyárfás and Sárközy showed that (Formula presented.). For (Formula presented.), we show that (Formula presented.) and therefore, (Formula presented.). 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 (Formula presented.), where (Formula presented.). Moreover, in each case, our results imply the existence of at least (Formula presented.) distinct induced rainbow paths on (Formula presented.) vertices. Along the way, we obtain some new results on an oriented variant of the Gyárfás–Sumner conjecture. For (Formula presented.), let (Formula presented.) denote the orientations of (Formula presented.) in which one vertex has out-degree or in-degree (Formula presented.). We show that every (Formula presented.) -free oriented graph having a chromatic number at least (Formula presented.) and every bikernel-perfect oriented graph with girth (Formula presented.) having a chromatic number at least (Formula presented.) contains every oriented tree on at most (Formula presented.) vertices as an induced subgraph. © 2024 Wiley Periodicals LLC.

Faculty Publications

Browse

Filters

Settings

Sort By

Results per page

Search Results