| 词条 | Meyniel graph |
| 释义 |
In graph theory, a Meyniel graph is a graph in which every odd cycle of length five or more has at least two chords, edges connecting non-consecutive vertices of the cycle.[1] The chords may be uncrossed (as shown in the figure) or they may cross each other, as long as there are at least two of them. The Meyniel graphs are named after Henri Meyniel (also known for Meyniel's conjecture), who proved that they are perfect graphs in 1976,[1] long before the proof of the strong perfect graph theorem completely characterized the perfect graphs. The same result was independently discovered by {{harvtxt|Markosjan|Karapetjan|1976}}.[2] PerfectionThe Meyniel graphs are a subclass of the perfect graphs. Every induced subgraph of a Meyniel graph is another Meyniel graph, and in every Meyniel graph the size of a maximum clique equals the minimum number of colors needed in a graph coloring. Thus, the Meyniel graphs meet the definition of being a perfect graph, that the clique number equals the chromatic number in every induced subgraph.[1][1][2] Meyniel graphs are also called the very strongly perfect graphs, because (as Meyniel conjectured and Hoàng proved) they can be characterized by a property generalizing the defining property of the strongly perfect graphs: in every induced subgraph of a Meyniel graph, every vertex belongs to an independent set that intersects every maximal clique.[1][3] Related graph classesThe Meyniel graphs contain the chordal graphs, the parity graphs, and their subclasses the interval graphs, distance-hereditary graphs, bipartite graphs, and line perfect graphs.[4] Although Meyniel graphs form a very general subclass of the perfect graphs, they do not include all perfect graphs. For instance the house graph (a pentagon with only one chord) is perfect but is not a Meyniel graph. Algorithms and complexityMeyniel graphs can be recognized in polynomial time,[5] and several graph optimization problems including graph coloring that are NP-hard for arbitrary graphs can be solved in polynomial time for Meyniel graphs.[6][7] References1. ^1 {{citation | last = Meyniel | first = H. | doi = 10.1016/S0012-365X(76)80008-8 | issue = 4 | journal = Discrete Mathematics | mr = 0439682 | pages = 339–342 | title = On the perfect graph conjecture | volume = 16 | year = 1976}}. 2. ^1 {{citation | last1 = Markosjan | first1 = S. E. | last2 = Karapetjan | first2 = I. A. | issue = 5 | journal = Doklady Akademiya Nauk Armyanskoĭ SSR | mr = 0450130 | pages = 292–296 | title = Perfect graphs | volume = 63 | year = 1976}}. 3. ^{{citation | last = Hoàng | first = C. T. | doi = 10.1016/0095-8956(87)90047-5 | issue = 3 | journal = Journal of Combinatorial Theory | mr = 888682 | pages = 302–312 | series = Series B | title = On a conjecture of Meyniel | volume = 42 | year = 1987}}. 4. ^1 2 3 Meyniel graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-25. 5. ^{{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}}. 6. ^{{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}}. 7. ^{{citation | last1 = Roussel | first1 = F. | last2 = Rusu | first2 = I. | doi = 10.1016/S0012-365X(00)00264-8 | issue = 1-3 | journal = Discrete Mathematics | mr = 1829840 | pages = 107–123 | title = An {{math|O(n2)}} algorithm to color Meyniel graphs | volume = 235 | year = 2001}}. 2 : Graph families|Perfect graphs |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。