What Are Perfect Graphs? | Baeldung on Computer Science

1. Overview

In this tutorial, we’ll explore the definition of the perfect graph and its theorem in depth. Then, we’ll examine its mathematical implications and the key characteristics of perfect graphs. In addition, we’ll look at how perfect graphs are used in practice. Finally, we define the Strongly Perfect and the Weakly Perfect, which are used to classify perfect graphs.

2. What Exactly Is Graph Theory?

The study of graphs in both computer science and mathematics is known as graph theory. A graph is a mathematical structure employed to construct pairwise relationships between objects in a collection. In this context, a graph is a collection of nodes, also known as vertices, and the edges that connect them:

The graph above demonstrates this:

Graph $G$ $(V, E)$
Vertices $V= {A, B, C, D}$
Edges $E = {AB, AC, BC, CD}$

3. What Are Perfect Graphs?

A graph $G$ is said to be perfect if and only if each induced subgraph of $G$ has a clique number equal to its chromatic number, in other words, $\omega(G) = \chi(G)$ . In this context, a non-perfect graph is known as an imperfect graph. Let’s study these characteristics in the following subsections.

3.1. Chromatic Number of a Graph

The least amount of colors necessary to color the vertices of a graph $G$ so that no two adjacent nodes have the same color is its chromatic number.

The chromatic number of a graph $G$ is most frequently written as $\chi(G)$ .

The graphs below show the minimal colorings and chromatic numbers for a selection of them:

3.2. Clique Number of a Graph

A clique is a vertex-induced subgraph of a complete graph. A set $C$ is a clique of an graph $G$ if and only if $C \subseteq V(G)$ and $U,V$ $\in C$ and $U$ $\neq V$ $\Rightarrow$ $U,V$ $\in E(G)$ .

A graph G’s clique number, denoted $\omega(G)$ , is the number of vertices in its maximum clique. It is equivalently the size of G’s largest clique or maximal clique.

As previously stated, a clique of a graph $G$ is a complete subgraph of $G$ . A clique is maximal if and only if it’s not a proper subgraph of another clique. A maximum clique of a graph $G$ is a clique with as many or more vertices as any other clique of $G$ .

The clique of a graph is illustrated in the graphs below, and the number of cliques for a single graph G is shown in red:

3.3. The Definition of Perfect Graphs

A graph $G = (V, E)$ is perfect graph if for all $S \subseteq V$ , $\omega(G[S]) = \chi(G[S])$ .

It means that the chromatic and clique number for each graph’s induced subgraphs must match for a graph to be considered perfect.

Let’s see some examples based on the following graphs:

Since the clique number $\omega(G)$ in a graph $G1$ equals the chromatic number $\chi(G)$ , it is a perfect graph. $\omega(G) = 2$ and $\chi(G) = 2$ , so $\omega(G) = \chi(G)$

However, the chromatic number $\chi(G)$ for graph $G2$ is 4, and the clique number $\omega(G)$ is 3. As a result, graph $G2$ is not a perfect graph.

Let $\G = (V, E)$ be a graph. A suitable coloring of $G$ is a function $f$ from $V$ to some set $R$ , so that $\f(x) = f(y)$ whenever $\ (x, y) \in E$ . The chromatic number of $G$ is the size of the smallest set $R$ for which there exists a suitable coloring of $G$ from $V$ to $R$ .

We denote by $\omega(G)$ the largest $G$ clique’s size and by $\chi(G)$ the chromatic number of $G$ . It is true for every graph $G$ that $\omega(G) \le \chi(G)$ . It is said that a graph is perfect if, for each induced subgraph $H$ of $G$ , $\omega(G) = \chi(G)$ .

A perfect cycle with three vertices is depicted in the graph below:

$C3$ Cycle with 3 vertices
Chromatic number $\chi(G) = 3$
Clique number $\omega(G) = 3$

A, B, and C are cliques in this graph, and the clique number is 3. Consequently, $\omega(C3)= 3$ since $\omega(G) = \chi(G)$ . Accordingly, the clique number of graph $G$ is equal to the chromatic number of graph $G$ . As a result, the $C3$ cycle graph is a perfect graph.

4. Strong Perfect Graph

A graph is strongly perfect if each induced subgraph H has a unique vertex set that satisfies each of H’s maximal cliques. Every strong perfect graph is perfect, but the opposite is not always true. The figure next presents a strong perfect graph:

5. Weak Perfect Graph

A graph is weakly perfect if $\omega(G)=\chi(G)$ . This condition must hold for induced subgraphs to say a graph is perfect, but there is no requirement that it does. The clique number is $\omega(G)$ , and the chromatic number is $\chi(G)$ . Thus, in every situation, weak perfect graphs exist. The following example shows a weak perfect graph:

5. Conclusions

This article covered perfect graphs, one of the most popular graph theories. At first, we discussed the perfect graph theorem. Then, to better understand the concepts, examples were used to explain the graphs’ chromatic and clique numbers. Finally, we presented both strong perfect graphs and weak perfect graphs. Readers will consequently have a thorough understanding of perfect graphs and their potential applications.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex