Editing Meyniel graph (section)

==Algorithms and complexity==
Meyniel graphs can be recognized in [[polynomial time]],<ref>{{citation
 | last1 = Burlet | first1 = M.
 | last2 = Fonlupt | first2 = J.
 | contribution = Polynomial algorithm to recognize a Meyniel graph
 | doi = 10.1016/S0304-0208(08)72938-4
 | mr = 778765
 | pages = 225–252
 | publisher = North-Holland, Amsterdam
 | series = North-Holland Math. Stud.
 | title = Topics on perfect graphs
 | volume = 88
 | year = 1984| hdl = 10068/49205
 | hdl-access = free
 }}.</ref> and several graph optimization problems including [[graph coloring]] that are [[NP-hard]] for arbitrary graphs can be solved in polynomial time for Meyniel graphs.<ref>{{citation
 | last = Hertz | first = A.
 | doi = 10.1016/0095-8956(90)90078-E
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 1081227
 | pages = 231–240
 | series = Series B
 | title = A fast algorithm for coloring Meyniel graphs
 | volume = 50
 | year = 1990| doi-access = free
 }}.</ref><ref>{{citation
 | last1 = Roussel | first1 = F.
 | last2 = Rusu | first2 = I.
 | doi = 10.1016/S0012-365X(00)00264-8
 | issue = 1–3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 1829840
 | pages = 107–123
 | title = An {{math|''O''(''n''<sup>2</sup>)}} algorithm to color Meyniel graphs
 | volume = 235
 | year = 2001| doi-access = free
 }}.</ref>