Scholars Central

Conference abstractPublished 18 Aug 2016

An efficient way to determine the chromatic number of a graph directly from its input realizable sequence

Authors: Prantik Biswas, Paritosh Bhattacharya

Jaypee Institute of Information Technology, India National Institute of Technology, India

Ask about this article

Abstract

Select any words in the title or abstract, or press this and choose a sentence.

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.

Ask about this article

Answers come only from this article's title, abstract and keywords, each sentence pointing to where it comes from. Your question is sent to OpenAI to write the answer. Scholars Central does not store it.

Try:

More from this journal

The newest in Medicinal Chemistry.

All its articles

Follow

New articles from what you follow go into your email digest, once you agree to alert emails.

  • JournalMedicinal Chemistry
  • SubjectChemistry
  • SubjectPharmaceutical Sciences
  • BylineArticles whose byline prints “Prantik Biswas”
  • BylineArticles whose byline prints “Paritosh Bhattacharya”