Prantik Biswas and Paritosh Bhattacharya
Jaypee Institute of Information Technology, India
National Institute of Technology, India
Posters & Accepted Abstracts: Med chem
Spectral graph theory is a popular topic in modern day applied mathematics. Spectral graph theoretic techniques are widely used to extract a large variety of information about different properties of a graph from its adjacency matrix. A well known physical property of a graph is its chromatic number. In this paper, we have proposed an efficient approach to determine chromatic number of a graph directly from a realizable sequence. The method involves construction of adjacency matrix corresponding to an input sequence followed by calculation of eigen values to determine the bounds of chromatic number and consequently its chromatic number. One of the most common properties of a square matrix is its eigen value. The study of graph eigen values realizes increasingly rich connections with many other frontiers of mathematics. The spectrum of a graph when analysed with eigen values, yields a good resemblance with most of the major invariants of a graph, linking one extremal property to another. In our work, we have proposed a methodology to predict the chromatic number directly from an input graphic sequence. The proposed algorithm first checks whether an input non-increasing sequence is realizable through the construction of adjacency matrix. If the sequence turns out to be graphic, it then computes the eigen value from the already constructed adjacency matrix of the input degree sequence. Next we use the well known interrelationships between eigen values and chromatic number of a graph to predict the bounds of chromatic number for the given realizable input sequence. Finally we compute chromatic number by applying a trial and error method.
Medicinal Chemistry received 6627 citations as per Google Scholar report
Spanish 
Chinese 
Russian 
German 
French 
Japanese 
Portuguese 
Hindi 