A fast algorithm for coloring Meyniel graphs

Berge, 1961, Färbung von Graphen, deren sämtliche beziehungsweise deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 114 Berge, 1983 Berge, 1984, Strongly perfect graphs, Vol. 21, 57 M. E. Bertschi, Perfectly contractile graphs, J. Combin. Theory Ser. B, in press. Burlet, 1984, Parity graphs, Vol. 21, 253 Grötschel, 1981, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169, 10.1007/BF02579273 Hertz, 1988, Perfectly orderable graphs are quasi-parity graphs: A short proof, Discrete Math., 68, 111, 10.1016/0012-365X(88)90047-7 Hoàng, 1987, On a conjecture of Meyniel, J. Combin. Theory Ser. B, 42, 302, 10.1016/0095-8956(87)90047-5 Meyniel, 1976, On the perfect graph conjecture, Discrete Math., 16, 339, 10.1016/S0012-365X(76)80008-8 Meyniel, 1984, The graphs whose odd cycles have at least two chords, Vol. 21, 115 Meyniel, 1987, A new property of critical imperfect graphs and some consequences, European J. Combin., 8, 313, 10.1016/S0195-6698(87)80037-9 Preissmann, 1985, A note on strong perfectness of graphs, Math. Programming, 31, 321, 10.1007/BF02591953 Ravindra, 1982, Meyniel graphs are strongly perfect, J. Combin. Theory Ser. B, 33, 187, 10.1016/0095-8956(82)90068-5 Whitesides, 1984, A method for solving certain graph recognition and optimization problems with applications to perfect graphs, Vol. 21, 281