Meyniel-diagram - Meyniel graph
I grafteori är ett Meyniel-diagram ett diagram där varje udda cykel med längden fem eller mer har minst två ackord, kanter som förbinder icke-på varandra följande hörn av cykeln. Ackorden kan vara okorsade (som visas i figuren) eller så kan de korsa varandra så länge det finns minst två av dem.
Meyniel-graferna är uppkallade efter Henri Meyniel (även känd för Meyniels antaganden ), som visade att de var perfekta grafer 1976, långt innan beviset på den starka perfekta grafsatsen kännetecknade helt de perfekta graferna. Samma resultat upptäcktes oberoende av Markosjan & Karapetjan (1976) .
Fulländning
Meyniel-graferna är en underklass av de perfekta graferna. Varje inducerad undergraf av ett Meyniel-diagram är ett annat Meyniel-diagram, och i varje Meyniel-diagram är storleken på en maximal klick lika med det minsta antalet färger som behövs för en graffärgning . Således uppfyller Meyniel-graferna definitionen av att vara en perfekt graf, att klickantalet är lika med det kromatiska antalet i varje inducerad subgraf.
Meyniel-grafer kallas också de mycket starkt perfekta graferna , för (som Meyniel antog och Hoàng visade) de kan karakteriseras av en egenskap som generaliserar den definierande egenskapen hos de starkt perfekta graferna : i varje inducerad undergraf av en Meyniel-graf tillhör varje toppunkt en oberoende uppsättning som skär varje maximal klick .
Relaterade diagramklasser
Meyniel-graferna innehåller ackorddiagram , paritetsdiagram och deras underklasser intervalldiagram , avstånds-ärftliga grafer , tvåpartsdiagram och perfekta linjediagram .
Även om Meyniel-grafer utgör en mycket allmän underklass av de perfekta graferna, inkluderar de inte alla perfekta grafer. Till exempel är husdiagrammet (en femkant med endast ett ackord) perfekt men är inte ett Meyniel-diagram.
Algoritmer och komplexitet
Meyniel-grafer kan kännas igen i polynomtid och flera grafoptimeringsproblem inklusive graffärgning som är NP-hårda för godtyckliga grafer kan lösas på polynomtid för Meyniel-grafer.