Characterization of diagrams by 0-1 inequalities

✍ Scribed by I.G. Rosenberg

• Publisher: Elsevier Science
• Year: 1987
• Tongue: English
• Weight: 696 KB
• Volume: 63
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(87)90015-x

✦ Synopsis

An orientation of an undirected graph is a 2-orientation if it is the cover relation of an order. The characterization of graphs admitting a 2-orientation is an old open problem. To a graph G we associate a system of O-1 inequalities whose unknowns are indexed by edges and inequalities by cycles of G so that the 2-orientations of G are in a one-to-one correspondence with the O-l solutions of the system. We discuss the redundancies of inequalities. The system may be used to exhibit and enumerate all the 2-orientations of G (this is done for K,,, K,, and some other graphs) or to prove that there is none (given for the Mycielski (Griitsch) graphs by a conceptually new argument). The inequalities are presented for the more general korientations. The machinery could be used to replace some combinatorial arguments by routine manipulations of O-l inequalities and open up the possibility of applying some of the techniques developed in O-l optimization to the diagram problem.