The Perfect Graph Conjecture For Toroidal Graphs

Document Type


Publication Date


Published In

North-Holland Mathematics Studies


This chapter discusses the perfect graph conjecture for toroidal graphs. Graphs are assumed to be finite without loops or multiple edges. The ω (G) is defined as the size of the largest complete subgraph of G, while γ (G) is defined as the vertex coloring number of G. A graph G is perfect only if G has property P. Each maximal clique of G intersects all but one maximal independent set of G, and vice versa. If G is toroidal and has property P, then G is perfect. In a critical toroidal graph G, either ω (G) < 4 or G is regular of degree six and triangulates the torus.

This document is currently not available here.