Polynomial -Binding Functions and Forbidden Induced Subgraphs: A Survey

A graph G with clique number (G) and chromatic number (G) is perfect if (H)=(H) for every induced subgraph H of G. A family G of graphs is called -bounded with binding function f if (G)f((G)) holds whenever GG and G is an induced subgraph of G. In this paper we will present a survey on polynomial -binding functions. Especially we will address perfect graphs, hereditary graphs satisfying the Vizing bound (+1), graphs having linear -binding functions and graphs having non-linear polynomial -binding functions. Thereby we also survey polynomial -binding functions for several graph classes defined in terms of forbidden induced subgraphs, among them 2K2-free graphs, Pk-free graphs, claw-free graphs, and diamond-free graphs.Families of-bound graphs are natural candidates for polynomial approximation algorithms for the vertex coloring problem. (Andras Gyarfas [42])