Faculty Publications

Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736

Publications by NITK Faculty

Browse

Author: search.filters.author.Basavaraju, M.Subject: search.filters.subject.Chromatic number

Search Results

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    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.
  • No Thumbnail Available
    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.