A Note on Lovász Characterization of Perfect Graphs

Abstract

A graph is perfect if, for every induced subgraph, the chromatic number equals the size of its largest clique. In 1972, Lovász established a fundamental characterization of perfect graphs, showing that a graph is perfect if and only if, for every induced subgraph, the product of the size of the largest independent set and the size of the largest clique is at least the number of vertices. His proof relied on the technique of vertex replication. In this paper, we present an alternative proof of Lovász's result that avoids vertex replication. As vertex replication does not in general preserve ‐perfection, the argument developed here applies to the study of ‐perfect graphs, a class introduced by Ravindra in 2011.