A charming class of perfectly orderable graphs (Q1193431): Difference between revisions

In a variety of settings (e.g. the jump number problem in the theory of posets) greedy algorithms are efficient and for important classes of objects produce optimal solutions in all cases. In this case a greedy algorithm on a linear ordering of the vertices is to produce an optimal coloring of the graph. Those graphs for which this is always so are perfectly orderable (PO) and are (V. Chvátal) a subclass of perfect graphs. A graph is weakly triangulated (WT) if neither \(G\) nor its complement \(\overline G\) contain an induced cycle of length 5. \(P_ k\) \((C_ k)\) denotes a chordless path (cycle) with \(k\) vertices. V. Chvátal asks whether a WT-graph with no induced \(P_ 5\) is PO. In this paper it is demonstrated that a WT-graph with no induced \(P_ 5\) and \(\overline P_ 6\) (or \(P_ 6\) and \(\overline P_ 5)\) is PO by demonstrating that such graphs are charming and that charming graphs are PO. A vertex \(v\) of \(G\) is charming if it is not the endpoint of a \(P_ 5\) in \(G\) and \(\overline G\) and if it does not lie on a \(C_ 5\) of \(G\). Furthermore, \(G\) is charming if every induced subgraph has a charming vertex. A key lemma is that \(G\) with a charming vertex \(v\) is PO if \(G-v\) is PO, with proof based on a result by Chvátal: \(G\) is PO if it admits an obstruction-free ordering, i.e., there is not a chordless path \(abcd\) (as labeled) with \(a<b\) and \(d<c\). One important observation is that existence of a charming ordering (in which \(v_ i\) is charming in the subgraph induced by \(\{v_ 1,v_ 2<v_ i\})\) can be determined in polynomial time, which represents an NP-escape from the general problem and therefore major progress for this class certainly.