Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T16:09:50.354Z Has data issue: false hasContentIssue false

The Strong Perfect Graph Conjecture for Planar Graphs

Published online by Cambridge University Press:  20 November 2018

Alan Tucker*
Affiliation:
State University of New York, Stony Brook, New York
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A graph G is called γ-perfect if ƛ (H) = γ(H) for every vertex-generated subgraph H of G. Here, ƛ(H) is the clique number of H (the size of the largest clique of H) and γ(H) is the chromatic number of H (the minimum number of independent sets of vertices that cover all vertices of H). A graph G is called α-perfect if α(H) = θ(H) for every vertex-generated subgraph H of G, where α (H) is the stability number of H (the size of the largest independent set of H) and θ(H) is the partition number of H (the minimum number of cliques that cover all vertices of H).

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1973