Faculty Publications
Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736
Publications by NITK Faculty
Browse
3 results
Search Results
Item Gallai’s Path Decomposition for 2-degenerate Graphs(Discrete Mathematics and Theoretical Computer Science, 2023) Anto, N.; Basavaraju, M.Gallai’s path decomposition conjecture states that if G is a connected graph on n vertices, then the edges of G can be decomposed into at most ⌈ n2 ⌉ paths. A graph is said to be an odd semi-clique if it can be obtained from a clique on 2k + 1 vertices by deleting at most k − 1 edges. Bonamy and Perrett asked if the edges of every connected graph G on n vertices can be decomposed into at most ⌊ n2 ⌋ paths unless G is an odd semi-clique. A graph G is said to be 2-degenerate if every subgraph of G has a vertex of degree at most 2. In this paper, we prove that the edges of any connected 2-degenerate graph G on n vertices can be decomposed into at most ⌊ n2 ⌋ paths unless G is a triangle. © 2023 by the author(s)Item Maximal induced matchings in K4-free and K5-free graphs(Elsevier B.V., 2024) Basavaraju, M.; van Leeuwen, E.J.; Saei, R.An induced matching in a graph is a set of edges whose endpoints induce a 1-regular subgraph. It is known that every graph on n vertices has at most 10n/5?1.5849n maximal induced matchings, and this bound is the best possible as any disjoint union of complete graphs K5 forms an extremal graph. It is also known that the bound drops to 3n/3?1.4423n when the graphs are restricted to the class of triangle-free (K3-free) graphs. The extremal graphs, in this case, are known to be the disjoint unions of copies of K3,3. Along the same line, we study the maximum number of maximal induced matchings when the graphs are restricted to K5-free graphs and K4-free graphs. We show that every K5-free graph on n vertices has at most 6n/4?1.5651n maximal induced matchings and the bound is the best possible obtained by any disjoint union of copies of K4. When the graphs are restricted to K4-free graphs, the upper bound drops to 8n/5?1.5158n, and it is achieved by the disjoint union of copies of the wheel graph W5. © 2024 The Author(s)Item 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.