Premium
A connection between a convex programming problem and the LYM property on perfect graphs
Author(s) -
Wei Victor K.
Publication year - 1988
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190120413
Subject(s) - mathematics , combinatorics , connection (principal bundle) , regular polygon , discrete mathematics , vertex (graph theory) , perfect graph , property (philosophy) , perfect graph theorem , graph , pathwidth , line graph , philosophy , geometry , epistemology
We derive three equivalent conditions on a perfect graph concerning the optimal solution of a convex programming problem, the length‐width inequality, and the simultaneous vertex covering by cliques and anticliques. By combining proof techniques including Lagrangian dual, Dilworth's Theorem, and Kuhn‐Tucker Theorem, we establish a strong connection between the three topics. This provides new insights into the structure of perfect graphs. The famous Lubell‐Yamamoto‐Meschalkin (LYM) Property or Sperner Property for partially ordered sets is a specialization of our results to a subclass of perfect graphs.