Bipolarizable graphs (Q912868)

Perfectly orderable graphs are those for which an order of the nodes can be found such that for any subgraph \(G'\) of G the sequential node coloring algorithm (``always use the smaller possible colour'') gives an optimal coloring for \(G'\). Bipolarisable graphs admit a perfect order such that for any chain \(P_ 4(a,b,c,d)\) of 4 nodes we have \(a>b\) and \(c<d\). This class of perfectly orderable graphs is compared with other known classes of perfectly orderable graph.