Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Perfect graph
Summary
In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.
The perfect graphs include many important families of graphs and serve to unify results relating colorings and cliques in those families. For instance, in all perfect graphs, the graph coloring problem, maximum clique problem, and maximum independent set problem can all be solved in polynomial time, despite their greater complexity for non-perfect graphs. In addition, several important minimax theorems in combinatorics, including Dilworth's theorem and Mirsky's theorem on partially ordered sets, Kőnig's theorem on matchings, and the Erdős–Szekeres theorem on monotonic sequences, can be expressed in terms of the perfection of certain associated graphs.
The perfect graph theorem states that the complement graph of a perfect graph is also perfect. The strong perfect graph theorem characterizes the perfect graphs in terms of certain forbidden induced subgraphs, leading to a polynomial time algorithm for testing whether a graph is perfect.
A clique in an undirected graph is a subset of its vertices that are all adjacent to each other.
A graph coloring assigns a color to each vertex so that each two adjacent vertices have different colors.
In particular, the vertices of any clique must all be assigned different colors, so the chromatic number (the minimum number of colors in any coloring) is always greater than or equal to the clique number, the number of vertices in the maximum clique. The perfect graphs are defined as the graphs for which these two numbers are equal, not just in the graph itself, but in every induced subgraph obtained by deleting some of its vertices.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.