The Perfect Graph Conjecture For Toroidal Graphs

Document Type

Article

Publication Date

1984

Published In

North-Holland Mathematics Studies

Abstract

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.

Share

COinS