(Ich habe diese Frage vor zwei Wochen bei MathOverflow gepostet , aber bisher ohne strenge Antwort.) Ich habe eine Frage zu Graphenbreitenmaßen ungerichteter einfacher Graphen. Es ist bekannt, dass cographs (Graphen, die durch Operationen der disjunkten Vereinigung und Komplementierung ausgehend...
Ich versuche einige Konzepte über modulare Zerlegung und Clique-Width- Graphen zu verstehen . In diesem Artikel ("On P4-tidy graphs") wird gezeigt, wie Optimierungsprobleme wie Clique-Number oder Chromatic-Number mit Modular Decomposition gelöst werden können. Das Lösen dieser Probleme durch...
Wenn wir eine Baumzerlegung eines Graphen mit der Breite w erhalten , gibt es verschiedene Möglichkeiten, wie wir ihn "schön" machen können. Insbesondere ist bekannt, dass es möglich ist, ihn in eine Baumzerlegung umzuwandeln, bei der der Baum binär ist und seine Höhe O ( log n ) beträgt . Dies...
Sei eine Klasse von Graphen mit begrenzter Cliquenbreite. In jedem Graphen in einige Kanten kontrahiert (zB zufällig). Ist jetzt die Clique-Breite noch begrenzt?GGGGGGG Für den Fall, dass es (allgemein) nicht mehr beschränkt ist, wäre ich sehr an einem Gegenbeispiel
CMSOL zählt die monadische Logik zweiter Ordnung, dh eine Logik von Graphen, bei der die Domäne die Menge von Scheitelpunkten und Kanten ist, es Prädikate für die Scheitelpunkt-Adjazenz und die Scheitelpunkt-Inzidenz gibt, es gibt eine Quantifizierung über Kanten, Scheitelpunkte, Kantensätze und...