Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
On Related Edges in Well-Covered Graphs without Cycles of Length 4 and 6
verfasst von : Vadim E. Levit, David Tankus
Erschienen in: Graph Theory, Computational Intelligence and Thought
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A graph is
well-covered
if every maximal independent set has the same cardinality. The recognition problem of well-covered graphs is known to be
co-NPC
. The complexity status of the problem is not known if the input is restricted to graphs with no cycles of length 4. We conjecture that the problem is polynomial if the input graph does not contain cycles of length 4 and 6, and prove several theorems supporting our conjecture.