Reducing prime graphs and recognizing circle graphs (Q1116953): Difference between revisions

A reduction theorem for prime (simple) graphs in \textit{W. H. Cunningham}'s sense [SIAM J. Algebraic Discrete Methods 3, 214-228 (1982; Zbl 0497.05031)] is presented. It says that every prime graph of order \(n>5\) contains a smaller prime graph of order n-1. As an application a polynomial algorithm for recognizing circle graphs in \((n^ 5)\) time is presented.

0 references

reviewed by

Maciej M. Sysło

0 references

Mathematics Subject Classification ID

0 references

0 references

reduction theorem

0 references

prime graph

0 references

MaRDI profile type

MaRDI publication profile

0 references

0 references

0 references

0 references

Graphic presentations of isotropic systems

0 references

Decomposition of Directed Graphs

0 references

Q4156464

0 references

A characterization of circle graphs

0 references

Q3328583

0 references

Q3934405

0 references

Connectivity in Matroids

0 references

Lectures on matroids

0 references

Q3708048

0 references

Recognizing circle graphs in polynomial time

0 references

Reconnaissance des graphes de cordes

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1116953

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Q3097395
@@ Property / cites work: Q3097395 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5635462
@@ Property / cites work: Q5635462 / rank @@
+Normal rank
@@ Property / cites work @@
+Isotropic systems
@@ Property / cites work: Isotropic systems / rank @@
+Normal rank
@@ Property / cites work @@
+Graphic presentations of isotropic systems
@@ Property / cites work: Graphic presentations of isotropic systems / rank @@
+Normal rank
@@ Property / cites work @@
+Decomposition of Directed Graphs
@@ Property / cites work: Decomposition of Directed Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4156464
@@ Property / cites work: Q4156464 / rank @@
+Normal rank
@@ Property / cites work @@
+A characterization of circle graphs
@@ Property / cites work: A characterization of circle graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3328583
@@ Property / cites work: Q3328583 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3934405
@@ Property / cites work: Q3934405 / rank @@
+Normal rank
@@ Property / cites work @@
+Connectivity in Matroids
@@ Property / cites work: Connectivity in Matroids / rank @@
+Normal rank
@@ Property / cites work @@
+Lectures on matroids
@@ Property / cites work: Lectures on matroids / rank @@
+Normal rank
@@ Property / cites work @@
+Q3708048
@@ Property / cites work: Q3708048 / rank @@
+Normal rank
@@ Property / cites work @@
+Recognizing circle graphs in polynomial time
@@ Property / cites work: Recognizing circle graphs in polynomial time / rank @@
+Normal rank
@@ Property / cites work @@
+Reconnaissance des graphes de cordes
@@ Property / cites work: Reconnaissance des graphes de cordes / rank @@
+Normal rank