A study on defective colouring of graphs

Title

A study on defective colouring of graphs

Creator

Thomas, Ellumkalayil Merlin - 1881508

Description

If different technology represent distinct colours that are to be located on some geographical region which can be represented as vertices of a graph, then the proper colouring is obtained when no two technology of same type share a common edge between the vertices they are placed on. The minimum technology required for such a colouring of a graph is the chromatic number of the graph. However, if the available technology are less than that of the minimum required, then the question arises on how to place the technology on the vertices of a graph in such a way that there is a minimum adjacency between the technology of same type. The solution for this problem can be attained by defining certain rules for the properness of colouring in which a few thresholds are tolerated. We know that, in a proper colouring every colour class is an independent set. If the available colours to colour a graph is less than that of the chromatic number of graphs, then a threshold that can be tolerated is permitting few colour classes to be non-independent set. An edge uv is said to be a monochromatic edge or bad edge if the colours assigned to both u and v are the same.

Publisher

CHRIST (Deemed to be University)

Subject

Mathematics

Language

English

Type

PhD