• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Hadwiger's Conjecture On Circular Arc Graphs

Belkale, Naveen 07 1900 (has links)
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 least k. In this thesis, we give motivation for attempting Hadwiger’s conjecture for circular arc graphs and also prove the conjecture for proper circular arc graphs. Circular arc graphs are graphs whose vertices can be represented as arcs on a circle such that any two vertices are adjacent if and only if their corresponding arcs intersect. Proper circular arc graphs are a subclass of circular arc graphs that have a circular arc representation where no arc is completely contained in any other arc. It is interesting to study Hadwiger’s conjecture for circular arc graphs as their clique minor cannot exceed beyond a constant factor of its chromatic number as We show in this thesis. Our main contribution is the proof of Hadwiger’s conjecture for proper circular arc graphs. Also, in this thesis we give an analysis and some basic results on Hadwiger’s conjecture for circular arc graphs in general.

Page generated in 0.0897 seconds