A study on defective colouring of graphs

Abstract

If different technology represents 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 number of 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. A near proper colouring of graphs is a colouring that minimises the number of monochromatic edges by permitting few colour classes to have adjacency between the elements in it. The minimum number of monochromatic edges obtained from near proper colouring is called near defect number, denoted by B_k (G). A and#948;^((k))-colouring of graph G is a near proper colouring of G consisting of k given colours, where 1and#8804;kand#8804;and#967;(G)-1, which minimises the number of monochromatic edges by permitting at most one colour class to have adjacency among the vertices in it. The and#948;^((k))-defect number is the minimum number of monochromatic edges obtained from a and#948;^((k))-colouring of graphs and it is denoted by b_k(G). The study concerned is the further work on a near proper colouring and a and#948;^((k))-colouring of graphs.