| Details: |
The problems related to the coloring of the graphs are widely associated with many modern day problems such as scheduling, networking etc. A coloring of a graph G is an assignment of colors to the vertices of G such that no two adjacent vertices receive the same color, and the chromatic number of G (denoted by χ(G)) is the minimum number of colors needed to color G. The coloring decision problem even for restricted classes of graphs is NP-complete. Thus the current research is on studying the lower and upper bounds for the chromatic number in terms of various other parameters of the given graph and in finding approximation algorithms for the chromatic number of some special graphs. A clique in a graph G is a set of mutually adjacent vertices, and the clique number of G (denoted by ω(G)) is the size of a maximum clique in G.
A class of graph C is said to be self complementary if a graph G is in C, then the complement graph of G is also in C. A class of graphs F is said to be near optimal colorable if there is a constant positive integer t, such that every graph G in F satisfies χ(G) ≤ max{t, ω(G)}. In this talk, we present a chromatic bound in terms of clique number for a self complementary class of graphs, namely the class of (P2 + P3, paraglider)-free graphs and a near optimal colorable class of graphs, namely the class of (P5, K5 - e)-free graphs.
|