Well-ordered graph

The greedy algorithm, when applied to a given ordering of the vertices of the graph G , sequentially considers the vertices of the graph (according to order) and assigns each vertex the first available color. Different ordering of vertices can lead to different numbers of required colors. There is always an ordering that leads to optimal coloring - this is true, for example, when ordering vertices according to the colors of the optimal coloring, but such ordering can happen, it is difficult to find. Well-ordered graphs, by definition, are graphs for which there is an ordering that is optimal for the greedy coloring algorithm, not only for the graph itself, but also for all of its generated subgraphs .

More formally, it is said that a graph G is completely orderable if there is an ordering π of the vertices of the graph G such that any generated subgraph of the graph G is optimally colored by the greedy coloring algorithm using the subsequence of ordering π generated by the vertices of the subgraph. The ordering π has this property exactly when there are no four vertices a , b , c and d for which abcd is a generated subgraph in which a stands for b (in ordering), and c stands for d ^{[1] [2 ]} .

Recognizing fully ordered graphs is an NP-complete problem ^{[3] [2]} . However, it is easy to verify whether a particular ordering is perfect (i.e., satisfying the requirements that the graph is completely ordered). Therefore, it is an NP-hard task to search for the perfect ordering of a graph, even if it is known in advance that the graph is completely orderable.

Any well-ordered graph is perfect . ^{[1] [2]}

The chordal graphs are well-ordered. A perfect order of chordal graphs can be found by reversing the ordering of a perfect exception for a graph. Thus, the application of the greedy coloring algorithm to perfect ordering provides an efficient chordal graph coloring algorithm. Comparability graphs are also completely orderable, where the perfect ordering is determined by the topological order of the transitive orientation of the graph ^{[1] [2]} .

Another class of completely ordered graphs consists of graphs G , such that in any subset of five vertices from a graph G at least one of the five vertices has a closed neighborhood that is a subset (or equal to) the closed neighborhoods of the other vertices of the five. Equivalently, these are graphs in which the partial order of closed neighborhoods defined by the inclusion of sets has a width not exceeding 4. A graph-cycle with 5 vertices has a partial order width of neighborhoods equal to five, so the number four is the maximum width providing perfect ordering. As in the case of chordal graphs (but, in the general case, not for completely ordered graphs in general), graphs with width four are recognized in polynomial time ^{[4] [5]} .

The concept between the order of perfect exclusion for chordal graphs and perfect ordering is the notion of the order of a half-perfect exception . In the concept of a perfect exception, there is no generated path from three vertices, in which the middle vertex is excluded first, and in the order of a half-perfect exception, there are no generated paths from four vertices, in which one of the middle vertices is removed before the others from the four. The reversal of such an ordering thus satisfies the requirements of a perfect ordering, so that the graphs with the order of a half-perfect exception are completely orderable ^{[6] [7]} . In particular, the lexicographic wide-search algorithm used to search for the perfect exclusion order for chordal graphs can be used to search for the order of a half-perfect exclusion of distance-inherited graphs , which, therefore, are also completely orderable ^[8] .

The graphs for which any ordering of vertices is perfect are cographs , simultaneously chordal, and distance-inherited graphs ^[9] . Since cographs do not contain the generated paths from the four vertices, they cannot violate the requirements of ordering the paths in perfect order.

Some other classes of well-ordered graphs are known ^{[10] [6] [11] [2] [12]} .

• Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. - SIAM Monographs on Discrete Mathematics and Applications, 1999. - ISBN 0-89871-432-X .
• Claude A. Christen, Stanley M. Selkow. Some perfect coloring properties of graphs // Journal of Combinatorial Theory . - 1979. - V. 27 , no. 1 . - pp . 49–59 . - DOI : 10.1016 / 0095-8956 (79) 90067-4 .
• Václav Chvátal. Topics in Perfect Graphs / Claude Berge, Václav Chvátal. - Amsterdam: North-Holland, 1984. - T. 21. - p. 63–68. - (Annals of Discrete Mathematics). . As quoted in Maffrey ( Maffray (2003 )).
• Václav Chvátal, Chính T. Hoàng, NVR Mahadev, D. De Werra. Four classes of perfectly orderable graphs // Journal of Graph Theory. - 1987. - Vol. 11 , no. 4 - p . 481–495 . - DOI : 10.1002 / jgt.3190110405 . .
• FF Dragan, F. Nicolai. LexBFS orderings of distance-hereditary graphs. - (Schriftenreihe des Fachbereichs Mathematik der Univ. Duisburg SM-DU-303). . As quoted in Bransthedt ( Brandstädt, Le & Spinrad (1999 )).
• Stefan Felsner, Vijay Raghavan, Jeremy Spinrad. Dilworth number // Order . - 2003. - V. 20 , no. 4 - p. 351–364 (2004) . - DOI : 10.1023 / B: ORDE.0000034609.99940.fb . .
• Chính T. Hoàng, Frédéric Maffray, Stephan Olariu, Myriam Preissmann. A charming class of perfectly graph graphs // Discrete Mathematics . - 1992. - V. 102 , no. 1 . - pp . 67–74 . - DOI : 10.1016 / 0012-365X (92) 90348-J . .
• Chính T. Hoàng, Bruce A. Reed. Some classes of perfectly orderable graphs // Journal of Graph Theory. - 1989. - Vol. 13 , no. 4 - p . 445-463 . - DOI : 10.1002 / jgt.3190130407 . .
• Frédéric Maffray. Bruce A. Reed, Cláudia L. Sales. - Springer-Verlag, 2003. - Vol. 11. - p. 65–84. - (CMS Books in Mathematics). - ISBN 0-387-95434-1 . - DOI : 10.1007 / 0-387-22444-0_3 . .
• Matthias Middendorf, Frank Pfeiffer. On the complexity of recognizing perfectly orderable graphs // Discrete Mathematics . - 1990. - T. 80 , no. 3 - pp . 327–333 . - DOI : 10.1016 / 0012-365X (90) 90251-C . .
• Charles Payan. Perfectness and Dilworth number // Discrete Mathematics . - 1983. - V. 44 , no. 2 - p . 229–230 . - DOI : 10.1016 / 0012-365X (83) 90064-X . .