Perfect Graph
Definition
A perfect graph is a graph $G$ where every induced subgraph $H$ satisfies the following. $$ \chi (H) = \omega (H) $$
- $\chi (H)$ is the chromatic number of graph $H$.
- $\omega (H)$ is the clique number of graph $H$.
Explanation
The world of graph theory, like many branches of mathematics, is staggeringly vast, honestly a bit more so. This is because there are so many different ways to define vertices and edges in graphs. Line graphs, of course, and even things that didn’t necessarily have to be graphs like interval graphs, are still graphs.
However, whether it is valuable is another issue. The cases where research in graphs is considered valuable can most easily be thought of as concerning graph coloring, connectivity, distance properties, etc. If a graph is just defined, it’s hard to get significant attention.
Among these, perfect graphs can be seen as specifically interested in graph coloring. For all graphs $H$, it’s naturally $$ \omega (H) \le \chi (H) $$ This is because if there are any subclique $K_{n}$, they obviously can’t be colored with just $n-1$ colors. A perfect graph excludes cases where the inequality applies, where anything but a clique must be colored with fewer colors.
Pure graph theory is viewed as a branch of combinatorics, and in problems about combinations, concepts like perfect graphs are bound to come up.