223:
the family, all larger graphs containing it as a substructure must also be excluded from the family. When this is true, there always exists an obstruction set (the set of graphs that are not in the family but whose smaller substructures all belong to the family). However, for some notions of what a substructure is, this obstruction set could be infinite. The
96:, in which a subdivision of one graph appears as a subgraph of the other. Thus, every graph either has a planar drawing (in which case it belongs to the family of planar graphs) or it has a subdivision of at least one of these two graphs as a subgraph (in which case it does not belong to the planar graphs).
222:
In order for a family to have a forbidden graph characterization, with a particular type of substructure, the family must be closed under substructures. That is, every substructure (of a given type) of a graph in the family must be another graph in the family. Equivalently, if a graph is not part of
1429:
Auer, Christopher; Bachmaier, Christian; Brandenburg, Franz J.; GleiĂner, Andreas; Hanauer, Kathrin; Neuwirth, Daniel; Reislhuber, Josef (2013), "Recognizing outer 1-planar graphs in linear time", in
Wismath, Stephen; Wolff, Alexander (eds.),
765:
1168:
1093:
1291:
150:
1221:
1051:
1194:
45:
can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these
1588:
Graph Theory and
Algorithms, 17th Symposium of Research Institute of Electric Communication, Tohoku University, Sendai, Japan, October 24-25, 1980, Proceedings
502:
1465:
219:
whether a given graph contains any of the members of the obstruction set, and therefore whether it belongs to the family defined by that obstruction set.
120:, structures, by specifying substructures that are forbidden to exist within any graph in the family. Different families vary in the nature of what is
1766:
Proceedings of the Eighth
Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977)
672:
1968:
1098:
2043:
1567:
1413:
1876:
1365:
1920:
1615:
1496:
109:
1351:
224:
2116:
1058:
1623:
1619:
1504:
1500:
183:
113:
42:
1989:
Jacobson, M. S.; KĂ©zdy, Andre E.; Lehel, Jeno (1997), "Recognizing intersection graphs of linear uniform hypergraphs",
1570:
180:, smaller graphs obtained by selecting a subset of the vertices and using all edges with both endpoints in that subset,
2171:
1324:
68:(can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the
1370:
981:
966:
777:
1340:
1226:
1991:
171:
81:
50:
2176:
1955:
1915:
903:
809:
461:
402:
61:
2166:
1761:
1635:
256:
190:), smaller graphs obtained from subgraphs by collapsing paths of degree-two vertices to single edges, or
2098:
1432:
21st
International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers
1680:
Beineke, L. W. (1968), "Derived graphs of digraphs", in Sachs, H.; Voss, H.-J.; Walter, H.-J. (eds.),
204:
The set of structures that are forbidden from belonging to a given graph family can also be called an
2181:
1380:
262:
131:
2112:"Forbidden Subgraphs for Graphs of Bounded Spectral Radius, with Applications to Equiangular Lines"
1456:
427:
357:
343:
324:
300:
93:
1559:
2125:
2016:
1830:
1786:
1662:
1644:
1542:
1516:
1478:
524:
1199:
215:
for testing whether a graph belongs to a given family. In many cases, it is possible to test in
2143:
1950:
1563:
1409:
1036:
434:
187:
1173:
2135:
2088:
2052:
2034:
2000:
1964:
1929:
1885:
1850:
1842:
1810:
1802:
1740:
1709:
1697:
1654:
1611:
1591:
1582:
Kashiwabara, Toshinobu (1981), "Algorithms for some intersection graphs", in Saito, Nobuji;
1526:
1470:
1435:
833:
578:
197:
177:
31:
2066:
2012:
1976:
1899:
1773:
1538:
2062:
2008:
1972:
1895:
1769:
1728:
1583:
1534:
1030:
931:
542:
530:
319:
216:
17:
1590:, Lecture Notes in Computer Science, vol. 108, Springer-Verlag, pp. 171â181,
623:
468:
152:
69:
2057:
1806:
2160:
1934:
1890:
1768:, Congressus Numerantium, vol. XIX, Winnipeg: Utilitas Math., pp. 311â315,
1745:
1666:
1627:
1375:
1303:
618:
572:
557:
294:
1530:
2020:
1546:
870:
837:
641:
611:
379:
174:, smaller graphs obtained from subsets of the vertices and edges of a larger graph,
65:
38:
1482:
1460:
1440:
994:
A finite list of forbidden induced subgraphs with minimum edge degree at least 2
849:
785:
665:
607:
487:
228:
193:
54:
1658:
2139:
1013:
862:
829:
653:
595:
590:
509:
117:
2147:
1596:
1474:
971:
A finite list of forbidden induced subgraphs with minimum degree at least 19
2111:
2079:
Yu, Yanming (2006), "More forbidden minors for wye-delta-wye reducibility",
1731:; Saito, Nobuji (1981), "Combinatorial problems on seriesâparallel graphs",
816:
781:
231:, a family that is closed under minors always has a finite obstruction set.
212:
1846:
1833:; Thilikos, Dimitrios M. (1999), "Graphs with branchwidth at most three",
1969:
10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K
2004:
1649:
1466:
Proc. 32nd IEEE Symposium on
Foundations of Computer Science (FOCS '91)
1434:, Lecture Notes in Computer Science, vol. 8242, pp. 107â118,
882:
1815:
1855:
1521:
1713:
2130:
760:{\displaystyle C_{4},C_{5},{\bar {C}}_{4}\left(=K_{2}+K_{2}\right)}
2093:
1019:
A finite list of at least 68 billion distinct (1,2,3)-clique sums
1408:, Graduate Texts in Mathematics, vol. 173, Springer-Verlag,
92:. For Kuratowski's theorem, the notion of containment is that of
866:
479:
1163:{\displaystyle \lambda \neq \beta _{m}^{1/2}+\beta _{m}^{-1/2}}
235:
List of forbidden characterizations for graphs and hypergraphs
30:"Forbidden minors" redirects here. The term may also refer to
27:
Describing a family of graphs by excluding certain (sub)graphs
137:
1953:(1997), "On line graphs of linear 3-uniform hypergraphs",
1700:(1988), "The complexity of some edge deletion problems",
196:, smaller graphs obtained from subgraphs by arbitrary
41:, a branch of mathematics, many important families of
1229:
1202:
1176:
1101:
1061:
1039:
675:
134:
1870:
Seinsche, D. (1974), "On a property of the class of
1507:(1993), "Linkless embeddings of graphs in 3-space",
1088:{\displaystyle \lambda <{\sqrt {2+{\sqrt {5}}}}}
1285:
1215:
1188:
1162:
1087:
1045:
759:
144:
2110:Jiang, Zilin; Polyanskii, Alexandr (2020-03-01).
211:Forbidden graph characterizations may be used in
2037:; Singhi, N. M. (1982), "Intersection graphs of
1055:A finite obstruction set exists if and only if
1793:-arboretum of graphs with bounded treewidth",
1509:Bulletin of the American Mathematical Society
60:A prototypical example of this phenomenon is
8:
1469:, IEEE Computer Society, pp. 802â811,
1286:{\displaystyle x^{m+1}=1+x+\dots +x^{m-1}}
967:Line graph of 3-uniform linear hypergraphs
2129:
2092:
2056:
1933:
1889:
1854:
1814:
1744:
1702:IEEE Transactions on Circuits and Systems
1648:
1595:
1520:
1439:
1399:
1397:
1395:
1271:
1234:
1228:
1207:
1201:
1175:
1150:
1143:
1138:
1121:
1117:
1112:
1100:
1076:
1068:
1060:
1038:
746:
733:
715:
704:
703:
693:
680:
674:
136:
135:
133:
1562:(1998) "Modern Graph Theory", Springer,
1329:A, possibly non-finite, obstruction set
577:Cycles of odd length 5 or more or their
238:
227:proves that, for the particular case of
2081:The Electronic Journal of Combinatorics
1391:
805:
498:
457:
1910:
1908:
883:Complement-reducible graphs (cographs)
276:A loop (for multigraphs) or triangle
7:
1918:(1978), "Trivially perfect graphs",
622:formed by removing an edge from the
261:Loops, pairs of parallel edges, and
1684:, Leipzig: Teubner, pp. 17â33
1628:"The strong perfect graph theorem"
25:
2044:European Journal of Combinatorics
106:forbidden graph characterization
1877:Journal of Combinatorial Theory
1531:10.1090/S0273-0979-1993-00335-5
64:, which states that a graph is
1461:"Computing planar intertwines"
709:
145:{\displaystyle {\mathcal {F}}}
1:
2117:Israel Journal of Mathematics
2058:10.1016/s0195-6698(82)80029-2
2033:Naik, Ranjan N.; Rao, S. B.;
1807:10.1016/S0304-3975(97)00228-4
986:-uniform linear hypergraphs,
1935:10.1016/0012-365X(78)90178-4
1891:10.1016/0095-8956(74)90063-X
1795:Theoretical Computer Science
1746:10.1016/0166-218X(81)90031-7
1733:Discrete Applied Mathematics
1441:10.1007/978-3-319-03841-4_10
1296:Subgraph / induced subgraph
525:Linklessly embeddable graphs
155:a forbidden substructure is
1682:BeitrÀge zur Graphentheorie
1325:induced-hereditary property
562:Cycles of length 4 or more
124:. In general, a structure
2198:
1659:10.4007/annals.2006.164.51
1404:Diestel, Reinhard (2000),
1371:Forbidden subgraph problem
1216:{\displaystyle \beta _{m}}
29:
18:Forbidden induced subgraph
2140:10.1007/s11856-020-1983-2
1764:(1977a), "Split graphs",
1352:RobertsonâSeymour theorem
1345:A finite obstruction set
1341:minor-hereditary property
1317:
514:A finite obstruction set
492:A finite obstruction set
378:
255:
225:RobertsonâSeymour theorem
1992:Graphs and Combinatorics
1916:Golumbic, Martin Charles
1597:10.1007/3-540-10704-5_15
1475:10.1109/SFCS.1991.185452
1308:three-vertex path graph
1046:{\displaystyle \lambda }
904:Trivially perfect graphs
128:is a member of a family
82:complete bipartite graph
2041:-uniform hypergraphs",
1956:Journal of Graph Theory
1366:ErdĆsâHajnal conjecture
1323:A family defined by an
1223:is the largest root of
1189:{\displaystyle m\geq 2}
186:subgraphs (also called
1847:10.1006/jagm.1999.1011
1762:Hammer, Peter Ladislaw
1339:A family defined by a
1287:
1217:
1190:
1164:
1089:
1047:
761:
658:Homeomorphic subgraph
399:Homeomorphic subgraph
165:forbidden substructure
146:
1835:Journal of Algorithms
1636:Annals of Mathematics
1288:
1218:
1191:
1165:
1090:
1048:
762:
596:9 forbidden subgraphs
473:Six forbidden minors
469:Outer 1-planar graphs
147:
1921:Discrete Mathematics
1874:-colorable graphs",
1698:Colbourn, Charles J.
1381:Zarankiewicz problem
1227:
1200:
1174:
1099:
1059:
1037:
950:, and complement of
673:
591:Line graph of graphs
403:Kuratowski's theorem
358:Triangle-free graphs
344:Comparability graphs
283:(for simple graphs)
132:
62:Kuratowski's theorem
1831:Bodlaender, Hans L.
1789:(1998), "A partial
1787:Bodlaender, Hans L.
1159:
1130:
1016:to a single vertex
915:and 4-vertex cycle
94:graph homeomorphism
2172:Graph minor theory
2005:10.1007/BF03353014
1951:Tyshkevich, Regina
1760:Földes, Stéphane;
1283:
1213:
1186:
1160:
1134:
1108:
1085:
1043:
757:
480:Auer et al. (2013)
435:Outerplanar graphs
188:topological minors
142:
104:More generally, a
2035:Shrikhande, S. S.
1696:El-Mallah, Ehab;
1612:Chudnovsky, Maria
1357:
1356:
1332:Induced subgraph
1318:General theorems
1311:Induced subgraph
1083:
1081:
1005:Induced subgraph
990: > 3
974:Induced subgraph
959:Induced subgraph
943:, 4-vertex cycle
924:Induced subgraph
896:Induced subgraph
769:Induced subgraph
712:
600:Induced subgraph
583:Induced subgraph
565:Induced subgraph
371:Induced subgraph
350:Induced subgraph
335:Induced subgraph
208:for that family.
198:edge contractions
178:induced subgraphs
167:might be one of:
16:(Redirected from
2189:
2152:
2151:
2133:
2107:
2101:
2097:
2096:
2076:
2070:
2069:
2060:
2030:
2024:
2023:
1986:
1980:
1979:
1949:Metelsky, Yury;
1946:
1940:
1938:
1937:
1912:
1903:
1902:
1893:
1867:
1861:
1859:
1858:
1827:
1821:
1819:
1818:
1783:
1777:
1776:
1757:
1751:
1749:
1748:
1729:Nishizeki, Takao
1727:Takamizawa, K.;
1724:
1718:
1716:
1693:
1687:
1685:
1677:
1671:
1669:
1652:
1632:
1608:
1602:
1600:
1599:
1584:Nishizeki, Takao
1579:
1573:
1557:
1551:
1549:
1524:
1493:
1487:
1485:
1452:
1446:
1444:
1443:
1426:
1420:
1418:
1401:
1292:
1290:
1289:
1284:
1282:
1281:
1245:
1244:
1222:
1220:
1219:
1214:
1212:
1211:
1195:
1193:
1192:
1187:
1169:
1167:
1166:
1161:
1158:
1154:
1142:
1129:
1125:
1116:
1094:
1092:
1091:
1086:
1084:
1082:
1077:
1069:
1052:
1050:
1049:
1044:
932:Threshold graphs
834:pentagonal prism
790:
766:
764:
763:
758:
756:
752:
751:
750:
738:
737:
720:
719:
714:
713:
705:
698:
697:
685:
684:
616:The four-vertex
543:Bipartite graphs
486:Graphs of fixed
428:Wagner's theorem
320:Claw-free graphs
239:
151:
149:
148:
143:
141:
140:
91:
79:
47:forbidden graphs
32:age restrictions
21:
2197:
2196:
2192:
2191:
2190:
2188:
2187:
2186:
2157:
2156:
2155:
2109:
2108:
2104:
2078:
2077:
2073:
2032:
2031:
2027:
1988:
1987:
1983:
1948:
1947:
1943:
1914:
1913:
1906:
1869:
1868:
1864:
1829:
1828:
1824:
1785:
1784:
1780:
1759:
1758:
1754:
1726:
1725:
1721:
1714:10.1109/31.1748
1695:
1694:
1690:
1679:
1678:
1674:
1630:
1616:Robertson, Neil
1610:
1609:
1605:
1581:
1580:
1576:
1558:
1554:
1497:Robertson, Neil
1495:
1494:
1490:
1457:Impagliazzo, R.
1454:
1453:
1449:
1428:
1427:
1423:
1416:
1403:
1402:
1393:
1389:
1362:
1267:
1230:
1225:
1224:
1203:
1198:
1197:
1172:
1171:
1097:
1096:
1057:
1056:
1035:
1034:
1031:spectral radius
1002: + 1
956:
949:
942:
921:
914:
893:
860:
827:
799:
788:
778:seriesâparallel
742:
729:
725:
721:
702:
689:
676:
671:
670:
651:
631:
531:Petersen family
451:
444:
421:
414:
396:
389:
368:
332:
308:
282:
265:of all lengths
237:
217:polynomial time
206:obstruction set
130:
129:
108:is a method of
102:
90:
84:
78:
72:
35:
28:
23:
22:
15:
12:
11:
5:
2195:
2193:
2185:
2184:
2179:
2177:Graph families
2174:
2169:
2159:
2158:
2154:
2153:
2124:(1): 393â421.
2102:
2071:
2025:
1999:(4): 359â367,
1981:
1963:(4): 243â251,
1941:
1928:(1): 105â107,
1904:
1884:(2): 191â193,
1862:
1841:(2): 167â194,
1822:
1778:
1752:
1719:
1708:(3): 354â362,
1688:
1672:
1650:math/0212070v1
1603:
1574:
1552:
1501:Seymour, P. D.
1488:
1447:
1421:
1414:
1390:
1388:
1385:
1384:
1383:
1378:
1373:
1368:
1361:
1358:
1355:
1354:
1349:
1346:
1343:
1336:
1335:
1333:
1330:
1327:
1320:
1319:
1315:
1314:
1312:
1309:
1306:
1304:Cluster graphs
1300:
1299:
1297:
1294:
1280:
1277:
1274:
1270:
1266:
1263:
1260:
1257:
1254:
1251:
1248:
1243:
1240:
1237:
1233:
1210:
1206:
1185:
1182:
1179:
1157:
1153:
1149:
1146:
1141:
1137:
1133:
1128:
1124:
1120:
1115:
1111:
1107:
1104:
1080:
1075:
1072:
1067:
1064:
1053:
1042:
1026:
1025:
1023:
1020:
1017:
1009:
1008:
1006:
1003:
998: â 3
992:
982:Line graph of
978:
977:
975:
972:
969:
963:
962:
960:
957:
954:
947:
940:
936:4-vertex path
934:
928:
927:
925:
922:
919:
912:
908:4-vertex path
906:
900:
899:
897:
894:
891:
887:4-vertex path
885:
879:
878:
876:
873:
858:
853:
846:
845:
843:
840:
825:
820:
813:
812:
806:Diestel (2000)
803:
800:
797:
792:
773:
772:
770:
767:
755:
749:
745:
741:
736:
732:
728:
724:
718:
711:
708:
701:
696:
692:
688:
683:
679:
668:
662:
661:
659:
656:
649:
644:
638:
637:
635:
632:
629:
624:complete graph
614:
604:
603:
601:
598:
593:
587:
586:
584:
581:
575:
573:Perfect graphs
569:
568:
566:
563:
560:
558:Chordal graphs
554:
553:
551:
548:
545:
539:
538:
536:
533:
527:
521:
520:
518:
515:
512:
506:
505:
499:Diestel (2000)
496:
493:
490:
483:
482:
477:
474:
471:
465:
464:
458:Diestel (2000)
455:
452:
449:
442:
437:
431:
430:
425:
422:
419:
412:
406:
405:
400:
397:
394:
387:
382:
376:
375:
372:
369:
366:
360:
354:
353:
351:
348:
346:
340:
339:
336:
333:
330:
322:
316:
315:
312:
309:
306:
297:
295:Linear forests
291:
290:
287:
284:
280:
273:
272:
269:
266:
259:
253:
252:
249:
246:
243:
236:
233:
202:
201:
191:
181:
175:
153:if and only if
139:
101:
98:
88:
76:
70:complete graph
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
2194:
2183:
2180:
2178:
2175:
2173:
2170:
2168:
2165:
2164:
2162:
2149:
2145:
2141:
2137:
2132:
2127:
2123:
2119:
2118:
2113:
2106:
2103:
2100:
2095:
2094:10.37236/1033
2090:
2086:
2082:
2075:
2072:
2068:
2064:
2059:
2054:
2050:
2046:
2045:
2040:
2036:
2029:
2026:
2022:
2018:
2014:
2010:
2006:
2002:
1998:
1994:
1993:
1985:
1982:
1978:
1974:
1970:
1966:
1962:
1958:
1957:
1952:
1945:
1942:
1936:
1931:
1927:
1923:
1922:
1917:
1911:
1909:
1905:
1901:
1897:
1892:
1887:
1883:
1879:
1878:
1873:
1866:
1863:
1857:
1852:
1848:
1844:
1840:
1836:
1832:
1826:
1823:
1817:
1812:
1808:
1804:
1801:(1â2): 1â45,
1800:
1796:
1792:
1788:
1782:
1779:
1775:
1771:
1767:
1763:
1756:
1753:
1747:
1742:
1738:
1734:
1730:
1723:
1720:
1715:
1711:
1707:
1703:
1699:
1692:
1689:
1683:
1676:
1673:
1668:
1664:
1660:
1656:
1651:
1646:
1643:(1): 51â229,
1642:
1638:
1637:
1629:
1625:
1624:Thomas, Robin
1621:
1620:Seymour, Paul
1617:
1613:
1607:
1604:
1598:
1593:
1589:
1585:
1578:
1575:
1572:
1569:
1568:0-387-98488-7
1565:
1561:
1560:BĂ©la BollobĂĄs
1556:
1553:
1548:
1544:
1540:
1536:
1532:
1528:
1523:
1518:
1514:
1510:
1506:
1505:Thomas, Robin
1502:
1498:
1492:
1489:
1484:
1480:
1476:
1472:
1468:
1467:
1462:
1458:
1451:
1448:
1442:
1437:
1433:
1425:
1422:
1417:
1415:0-387-98976-5
1411:
1407:
1400:
1398:
1396:
1392:
1386:
1382:
1379:
1377:
1376:Matroid minor
1374:
1372:
1369:
1367:
1364:
1363:
1359:
1353:
1350:
1347:
1344:
1342:
1338:
1337:
1334:
1331:
1328:
1326:
1322:
1321:
1316:
1313:
1310:
1307:
1305:
1302:
1301:
1298:
1295:
1278:
1275:
1272:
1268:
1264:
1261:
1258:
1255:
1252:
1249:
1246:
1241:
1238:
1235:
1231:
1208:
1204:
1183:
1180:
1177:
1155:
1151:
1147:
1144:
1139:
1135:
1131:
1126:
1122:
1118:
1113:
1109:
1105:
1102:
1078:
1073:
1070:
1065:
1062:
1054:
1040:
1032:
1028:
1027:
1024:
1021:
1018:
1015:
1011:
1010:
1007:
1004:
1001:
997:
993:
991:
989:
985:
980:
979:
976:
973:
970:
968:
965:
964:
961:
958:
953:
946:
939:
935:
933:
930:
929:
926:
923:
918:
911:
907:
905:
902:
901:
898:
895:
890:
886:
884:
881:
880:
877:
874:
872:
868:
864:
857:
854:
851:
848:
847:
844:
841:
839:
835:
831:
824:
821:
818:
815:
814:
811:
807:
804:
801:
796:
793:
787:
783:
779:
775:
774:
771:
768:
753:
747:
743:
739:
734:
730:
726:
722:
716:
706:
699:
694:
690:
686:
681:
677:
669:
667:
664:
663:
660:
657:
655:
648:
645:
643:
642:Ladder graphs
640:
639:
636:
633:
628:
625:
621:
620:
619:diamond graph
615:
613:
612:cactus graphs
609:
606:
605:
602:
599:
597:
594:
592:
589:
588:
585:
582:
580:
576:
574:
571:
570:
567:
564:
561:
559:
556:
555:
552:
549:
546:
544:
541:
540:
537:
534:
532:
528:
526:
523:
522:
519:
516:
513:
511:
508:
507:
504:
500:
497:
494:
491:
489:
485:
484:
481:
478:
475:
472:
470:
467:
466:
463:
459:
456:
453:
448:
441:
438:
436:
433:
432:
429:
426:
423:
418:
411:
408:
407:
404:
401:
398:
393:
386:
383:
381:
380:Planar graphs
377:
373:
370:
365:
361:
359:
356:
355:
352:
349:
347:
345:
342:
341:
337:
334:
329:
326:
323:
321:
318:
317:
313:
310:
305:
302:
298:
296:
293:
292:
288:
285:
279:
275:
274:
270:
267:
264:
260:
258:
254:
250:
247:
245:Obstructions
244:
241:
240:
234:
232:
230:
226:
220:
218:
214:
209:
207:
199:
195:
192:
189:
185:
182:
179:
176:
173:
170:
169:
168:
166:
162:
159:contained in
158:
154:
127:
123:
119:
115:
111:
107:
99:
97:
95:
87:
83:
75:
71:
67:
63:
58:
56:
52:
49:as (induced)
48:
44:
40:
33:
19:
2167:Graph theory
2121:
2115:
2105:
2084:
2080:
2074:
2048:
2042:
2038:
2028:
1996:
1990:
1984:
1960:
1954:
1944:
1925:
1919:
1881:
1880:, Series B,
1875:
1871:
1865:
1838:
1834:
1825:
1798:
1794:
1790:
1781:
1765:
1755:
1739:(1): 75â76,
1736:
1732:
1722:
1705:
1701:
1691:
1681:
1675:
1640:
1634:
1606:
1587:
1577:
1555:
1522:math/9301216
1515:(1): 84â89,
1512:
1508:
1491:
1464:
1450:
1431:
1424:
1406:Graph Theory
1405:
1348:Graph minor
1022:Graph minor
1014:ÎY-reducible
999:
995:
987:
983:
951:
944:
937:
916:
909:
888:
875:Graph minor
871:Wagner graph
855:
842:Graph minor
838:Wagner graph
822:
802:Graph minor
794:
776:2-connected
666:Split graphs
646:
634:Graph minor
626:
617:
608:Graph unions
535:Graph minor
517:Graph minor
495:Graph minor
476:Graph minor
454:Graph minor
446:
439:
424:Graph minor
416:
409:
391:
384:
363:
327:
311:Graph minor
303:
286:Graph minor
277:
229:graph minors
221:
210:
205:
203:
194:graph minors
184:homeomorphic
164:
160:
156:
125:
121:
112:a family of
105:
103:
85:
73:
59:
46:
39:graph theory
36:
2182:Hypergraphs
2051:: 159â172,
1455:Gupta, A.;
850:Branchwidth
786:branchwidth
579:complements
547:Odd cycles
510:Apex graphs
374:Definition
338:Definition
314:Definition
289:Definition
271:Definition
2161:Categories
2131:1708.02317
1816:1874/18312
1387:References
1029:Graphs of
863:octahedron
830:octahedron
791:†2)
784:†2,
654:dual graph
251:Reference
213:algorithms
118:hypergraph
110:specifying
100:Definition
2148:1565-8511
1856:1874/2734
1667:119151552
1276:−
1262:⋯
1205:β
1181:≥
1145:−
1136:β
1110:β
1106:≠
1103:λ
1063:λ
1041:λ
852:†3
819:†3
817:Treewidth
782:treewidth
710:¯
550:Subgraph
362:Triangle
268:Subgraph
248:Relation
172:subgraphs
122:forbidden
1626:(2006),
1586:(eds.),
1459:(1991),
1360:See also
1196:, where
1170:for any
1033:at most
652:and its
80:and the
51:subgraph
2099:Website
2067:0670849
2021:9173731
2013:1485929
1977:1459889
1900:0337679
1774:0505860
1547:1110662
1539:1164063
1012:Graphs
257:Forests
242:Family
163:. The
2146:
2065:
2019:
2011:
1975:
1898:
1772:
1665:
1566:
1545:
1537:
1483:209133
1481:
1412:
810:p. 327
789:
503:p. 275
462:p. 107
263:cycles
66:planar
43:graphs
2126:arXiv
2017:S2CID
1663:S2CID
1645:arXiv
1631:(PDF)
1543:S2CID
1517:arXiv
1479:S2CID
488:genus
116:, or
114:graph
55:minor
2144:ISSN
1571:p. 9
1564:ISBN
1410:ISBN
1095:and
1066:<
867:cube
529:The
445:and
415:and
390:and
325:Star
301:star
299:and
2136:doi
2122:236
2089:doi
2053:doi
2001:doi
1965:doi
1930:doi
1886:doi
1851:hdl
1843:doi
1811:hdl
1803:doi
1799:209
1741:doi
1710:doi
1655:doi
1641:164
1592:doi
1527:doi
1471:doi
1436:doi
650:2,3
610:of
450:2,3
420:3,3
395:3,3
331:1,3
307:1,3
157:not
89:3,3
53:or
37:In
2163::
2142:.
2134:.
2120:.
2114:.
2087:,
2085:13
2083:,
2063:MR
2061:,
2047:,
2015:,
2009:MR
2007:,
1997:13
1995:,
1973:MR
1971:,
1961:25
1959:,
1926:24
1924:,
1907:^
1896:MR
1894:,
1882:16
1849:,
1839:32
1837:,
1809:,
1797:,
1770:MR
1735:,
1706:35
1704:,
1661:,
1653:,
1639:,
1633:,
1622:;
1618:;
1614:;
1541:,
1535:MR
1533:,
1525:,
1513:28
1511:,
1503:;
1499:;
1477:,
1463:,
1394:^
1293:.
869:,
865:,
861:,
836:,
832:,
828:,
808:,
501:,
460:,
57:.
2150:.
2138::
2128::
2091::
2055::
2049:3
2039:k
2003::
1967::
1939:.
1932::
1888::
1872:n
1860:.
1853::
1845::
1820:.
1813::
1805::
1791:k
1750:.
1743::
1737:3
1717:.
1712::
1686:.
1670:.
1657::
1647::
1601:.
1594::
1550:.
1529::
1519::
1486:.
1473::
1445:.
1438::
1419:.
1279:1
1273:m
1269:x
1265:+
1259:+
1256:x
1253:+
1250:1
1247:=
1242:1
1239:+
1236:m
1232:x
1209:m
1184:2
1178:m
1156:2
1152:/
1148:1
1140:m
1132:+
1127:2
1123:/
1119:1
1114:m
1079:5
1074:+
1071:2
1000:k
996:k
988:k
984:k
955:4
952:C
948:4
945:C
941:4
938:P
920:4
917:C
913:4
910:P
892:4
889:P
859:5
856:K
826:5
823:K
798:4
795:K
780:(
754:)
748:2
744:K
740:+
735:2
731:K
727:=
723:(
717:4
707:C
700:,
695:5
691:C
687:,
682:4
678:C
647:K
630:4
627:K
447:K
443:4
440:K
417:K
413:5
410:K
392:K
388:5
385:K
367:3
364:K
328:K
304:K
281:3
278:K
200:.
161:G
138:F
126:G
86:K
77:5
74:K
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.