Perfect graphs and norms

Perfect graphs and norms

0.00 Avg rating0 Votes
Article ID: iaor1993305
Country: Netherlands
Volume: 51
Issue: 2
Start Page Number: 269
End Page Number: 272
Publication Date: Sep 1991
Journal: Mathematical Programming (Series A)
Authors:
Abstract:

For a given undirected graph equ1with n vertices the paper defines four norms on equ2, namely equ3where equ4(resp. equ5) stands for the family of all maximal cliques in G (resp. equ6, the complement of G). The goal of this note is to demonstrate the usefulness of some notions and techniques from functional analysis >l11<in graph theory by showing how Theorem 2.1 (G is equ7-perfect if and only if the norms equ8equ9are equal) together with >l10<the reflexivity of the space equ10equipped with either of the norms above easily yield one new result (Theorem 2.2) and two known characterizations of perfect graphs (Theorems 2.3-2.4). Namely, Theorem 2.2 provides a characterization of equ11-perfection that is strongly related to that of Lovász. It implies that the Lovász inequality is exactly the classical Schwartz inequality for the space, equ12restricted to (0, 1) vectors x, y satisfying x=y. Theorem 2.3 is well known as the Perfect Graph Theorem, while Theorem 2.4, due to V. Chvátal and D.R. Fulkerson, characterizes equ13-perfection of a graph G in terms of the equality between the vertex packing polytope of G and the fractional vertex packing polytope of G.

Reviews

Required fields are marked *. Your email address will not be published.