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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom