Chromatic number of special classes of graphs
Keywords:
Chromatic Number (χ(G)), Graph Coloring, Special Graph Classes, Perfect Graphs, Planar Graphs, Bipartite Graphs, Chordal Graphs, Clique Number (ω(G)), Graph Homomorphisms, Brooks' Theorem, Four Color Theorem, Edge Coloring, List Coloring, Fractional Chromatic Number, Graph Operations, Forbidden Subgraphs, Intersection Graphs, Coloring Algorithms, Computational Complexity, Extremal Graph TheoryAbstract
The chromatic number, denoted χ(G), represents one of the most fundamental and extensively studied parameters in graph theory, quantifying the minimum number of colors required to color the vertices of a graph G such that no two adjacent vertices share the same color. This comprehensive research investigates the chromatic numbers of special classes of graphs—mathematical structures with specific structural properties that enable deeper theoretical analysis and often permit exact chromatic number determination or tight bounds. The study encompasses both classical graph families (perfect graphs, planar graphs, bipartite graphs, chordal graphs) and emerging special classes (distance-hereditary graphs, claw-free graphs, circle graphs, intersection graphs of geometric objects) while exploring connections to computational complexity, algorithm design, and real-world applications in scheduling, register allocation, frequency assignment, and network design.
References
Jensen, T.R., Toft, B. (1995). Graph Coloring Problems. Wiley-Interscience.
Bondy, J.A., Murty, U.S.R. (2008). Graph Theory. Springer.
Diestel, R. (2017). Graph Theory (5th ed.). Springer.
Golumbic, M.C. (2004). Algorithmic Graph Theory and Perfect Graphs (2nd ed.). Elsevier.
Brandstädt, A., Le, V.B., Spinrad, J.P. (1999). Graph Classes: A Survey. SIAM.
