The Sum and Product of Chromatic Numbers of Graphs and their Line Graphs
C. Susanth *
Department of Mathematics, Research and Development Centre, Bharathiar University, Coimbatore - 641046, Tamilnadu, India.
Sunny Joseph Kalayathankal
Department of Mathematics, Kuriakose Elias College, Mannanam, Kottayam - 686561, Kerala, India.
*Author to whom correspondence should be addressed.
Abstract
The bounds on the sum and product of chromatic numbers of a graph and its complement are known as Nordhaus-Gaddum inequalities. In this paper, some variations on this result is studies. First, recall their theorem, which gives bounds on the sum and the product of the chromatic number of a graph with that of its complement. We also provide a new characterization of the certain graph classes.
Keywords: Chromatic number of a graph, chromatic index of a graph, line graph.