• Guarding Terrain using k-Watchtowers 

      Tripathi, Nitesh
      The discrete k-watchtower problem for a polyhedral terrain T in R3 with n vertices is to nd k vertical segments, called watchtowers, of smallest height, whose bottom end-points (bases) lie on some vertices of T, and ...
    • Hadwiger's Conjecture On Circular Arc Graphs 

      Belkale, Naveen (2009-04-30)
      Conjectured in 1943, Hadwiger’s conjecture is one of the most challenging open problems in graph theory. Hadwiger’s conjecture states that if the chromatic number of a graph G is k, then G has a clique minor of size at ...
    • The Isoperimetric Problem On Trees And Bounded Tree Width Graphs 

      Bharadwaj, Subramanya B V (2010-08-26)
      In this thesis we study the isoperimetric problem on trees and graphs with bounded treewidth. Let G = (V,E) be a finite, simple and undirected graph. For let δ(S,G)= {(u,v) ε E : u ε S and v ε V – S }be the edge boundary ...
    • On Dimensional Parameters Of Graphs And Posets 

      Adiga, Abhijin (2013-06-21)
      In this thesis we study the following dimensional parameters : boxicity, cubicity, threshold dimension and poset dimension. While the first three parameters are defined on graphs, poset dimension is defined on partially ...
    • Parameterized Complexity of Maximum Edge Coloring in Graphs 

      Goyal, Prachi (2018-03-09)
      The classical graph edge coloring problem deals in coloring the edges of a given graph with minimum number of colors such that no two adjacent edges in the graph, get the same color in the proposed coloring. In the following ...
    • Problems on bend-number, circular separation dimension and maximum edge 2-colouring 

      Lahiri, Abhiruk
      Representation of graphs as the intersection graphs of geometric objects has a long history. The objective is to a nd a collection of \simple" sets S such that a given graph G is its intersection graph. We are interested ...