Unterteilungsgraph

Ein Unterteilungsgraph ist in der Graphentheorie ein Graph, der durch Kantenunterteilung aus einem anderen Graph entstanden ist. Zwei Graphen heißen homöomorph, falls sie Unterteilungsgraphen besitzen, die isomorph sind. Unterteilungsgraphen spielen unter anderem im Satz von Kuratowski und in der Hajós-Vermutung eine wichtige Rolle.