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