22:
689:
681:
295:
288:
281:
274:
267:
260:
253:
246:
240:
697:
916:; that is, complementarily, testing whether a graph is well-covered is coNP-complete. Although it is easy to find maximum independent sets in graphs that are known to be well-covered, it is also NP-hard for an algorithm to produce as output, on all graphs, either a maximum independent set or a guarantee that the input is not well-covered.
156:, although they are meaningful for disconnected graphs as well. Some later authors have replaced the connectivity requirement with the weaker requirement that a well-covered graph must not have any isolated vertices. For both connected well-covered graphs and well-covered graphs without isolated vertices, there can be no
873:, or equivalently the well-covered maximal planar graphs. Every maximal planar graph with five or more vertices has vertex connectivity 3, 4, or 5. There are no well-covered 5-connected maximal planar graphs, and there are only four 4-connected well-covered maximal planar graphs: the graphs of the
655:
is a tree with more than two vertices, it is well-covered if and only if each non-leaf node of the tree is adjacent to exactly one leaf. The same characterization applies to graphs that are locally tree-like, in the sense that low-diameter neighborhoods of every vertex are acyclic: if a graph has
112:
is a set of vertices that touches every edge in the graph. A vertex cover is minimal, or irredundant, if removing any vertex from it would destroy the covering property: the removal would cause some edge to become uncovered. It is minimum if there is no other vertex cover with fewer vertices. A
113:
well-covered graph is one in which every minimal cover is also minimum. In the original paper defining well-covered graphs, Plummer writes that this is "obviously equivalent" to the property that every two minimal covers have the same number of vertices as each other.
148:
is a minimum vertex cover if and only if its complement is a maximum independent set. Therefore, a well-covered graph is, equivalently, a graph in which every maximal independent set has the same size, or a graph in which every maximal independent set is maximum.
543:
to be a well-covered graph (possibly disconnected, but with no isolated vertices) in which each maximal independent set (and therefore also each minimal vertex cover) contains exactly half of the vertices. This definition includes the rooted products of a graph
1297:
The complete graphs on 1, 2, 3, and 4 vertices are all maximal planar and well-covered; their vertex connectivity is either unbounded or at most three, depending on details of the definition of vertex connectivity that are irrelevant for larger maximal planar
556:: in a bipartite graph without isolated vertices, both sides of any bipartition form maximal independent sets (and minimal vertex covers), so if the graph is well-covered both sides must have equally many vertices. In a well-covered graph with
838:
to replace some of the path nodes (and the other two fragments for the remaining nodes) is a 1-vertex-connected cubic well-covered graph. All 1-vertex-connected cubic well-covered graphs have this form, and all such graphs are planar.
443:
so that no two rooks are attacking each other, it is always possible to continue placing more non-attacking rooks until there is one on every row and column of the chessboard. The graph whose vertices are the diagonals of a
1083:
The rook's graphs are, equivalently, the line graphs of complete bipartite graphs, so the well-covered property of rook's graphs is equivalent to the fact that complete bipartite graphs are equimatchable, for which see
448:
and whose edges connect pairs of diagonals that cross each other is well-covered, because its maximal independent sets are triangulations of the polygon and all triangulations have the same number of edges.
394:
A non-attacking placement of eight rooks on a chessboard. If fewer than eight rooks are placed in a non-attacking way on a chessboard, they can always be extended to eight rooks that remain non-attacking.
651:
Trees are a special case of bipartite graphs, and testing whether a tree is well-covered can be handled as a much simpler special case of the characterization of well-covered bipartite graphs: if
973:
The characterizations of well-covered graphs with girth five or more, and of well-covered graphs that are 3-regular, also lead to efficient polynomial time algorithms to recognize these graphs.
966:. The only connected randomly matchable graphs are the complete graphs and the balanced complete bipartite graphs. It is possible to test whether a line graph, or more generally a
404:
of length four or five is well-covered: in each case, every maximal independent set has size two. A cycle of length seven, and a path of length three, are also well-covered. Every
191:. A simplicial complex is said to be pure if all its maximal simplices have the same cardinality, so a well-covered graph is equivalently a graph with a pure independence complex.
1141:, Lemma 3.2. This source states its results in terms of the purity of the independence complex, and uses the term "fully-whiskered" for the special case of the rooted product.
900:
disjoint triangle faces, then these faces will form a clique cover. Therefore, the clique cover construction, which for these graphs consists of subdividing each of these
1353:
672:
greater than one has exactly one neighbor of degree one. A closely related but more complex characterization applies to well-covered graphs of girth five or more.
991:. Plummer uses "point" to mean a vertex in a graph, "line" to mean an edge, and "point cover" to mean a vertex cover; this terminology has fallen out of use.
889:) with 12 vertices, 30 edges, and 20 triangular faces. However, there are infinitely many 3-connected well-covered maximal planar graphs. For instance, if a
935:
consisting of the edges that satisfy the two properties of a matched edge in a very well covered graph, and then use a matching algorithm to test whether
842:
There are two types of 2-vertex-connected cubic well-covered graphs. One of these two families is formed by replacing the nodes of a cycle by fragments
33:. The three red vertices form one of its 14 equal-sized maximal independent sets, and the six blue vertices form the complementary minimal vertex cover.
2028:
798:
The 1- and 2-connected cubic well-covered graphs are all formed by replacing the nodes of a path or cycle by three fragments of graphs which
416:
is well covered if the two sides of its bipartition have equal numbers of vertices, for these are its only two maximal independent sets. The
869:
Complementing the characterization of well-covered simple polyhedra in three dimensions, researchers have also considered the well-covered
80:
whose vertices represent squares of a chessboard and edges represent moves of a chess rook. Known characterizations of the well-covered
428:
is well-covered: it has no independent sets larger than two, and every single vertex can be extended to a two-vertex independent set.
516:
formed by adding another vertex to each clique is well-covered; the rooted product is the special case of this construction when
2391:
Tankus, David; Tarsi, Michael (1997), "The structure of well-covered graphs and the complexity of their recognition problems",
1117:; they are also (together with the four-edge cycle, which is also well-covered) exactly the graphs whose domination number is
57:
if removing any vertex from it would leave some edge uncovered. Equivalently, well-covered graphs are the graphs in which all
1503:
567:, so very well covered graphs are the well covered graphs in which the maximum independent set size is as large as possible.
1124:. Its well-covering property is also stated in different terminology (having a pure independence complex) as Theorem 4.4 of
1685:
605:. The characterization in terms of matchings can be extended from bipartite graphs to very well covered graphs: a graph
1979:
Fink, J. F.; Jacobson, M. S.; Kinch, L. F.; Roberts, J. (1985), "On graphs having domination number half their order",
1798:
Finbow, A.; Hartnell, B.; Nowakowski, R. J. (1993), "A characterization of well covered graphs of girth 5 or greater",
2161:
1683:
Dochtermann, Anton; Engström, Alexander (2009), "Algebraic properties of edge ideals via combinatorial topology",
939:
has a perfect matching. Some problems that are NP-complete for arbitrary graphs, such as the problem of finding a
692:
A cubic 1-connected well-covered graph, formed by replacing each node of a six-node path by one of three fragments
2393:
2360:
2126:
1800:
1721:
760:
117:
2106:
Graph Theory and
Combinatorics: Proceedings of the Cambridge Combinatorial Conference, in Honour of Paul Erdős
904:
triangles into three new triangles meeting at a central vertex, produces a well-covered maximal planar graph.
2257:
1775:
Finbow, A.; Hartnell, B.; Nowakowski, R. (1988), "Well-dominated graphs: a collection of well-covered ones",
1948:
1911:
1874:
1837:
1359:; additional examples can be constructed by an operation they call an O-join for combining smaller graphs.
153:
2104:
Lesk, M.; Plummer, M. D.; Pulleyblank, W. R. (1984), "Equi-matchable graphs", in Bollobás, Béla (ed.),
1777:
1754:
1570:
764:
1055:
1053:
2285:
717:
602:
548:
and a one-edge graph. It also includes, for instance, the bipartite well-covered graphs studied by
461:
413:
160:, vertices which belong to every minimum vertex cover. Additionally, every well-covered graph is a
73:
2434:
2329:
1486:
Graph theory and algorithms (Proc. Sympos., Res. Inst. Electr. Comm., Tohoku Univ., Sendai, 1980)
1050:
129:
58:
2280:
1644:
Cook, David II; Nagel, Uwe (2010), "Cohen-Macaulay graphs and face vectors of flag complexes",
492:
together with the degree-one neighbors of the complementary set, and must therefore have size
831:
669:
408:
is well-covered: every maximal independent set consists of a single vertex. Similarly, every
1631:, Annals of Discrete Mathematics, vol. 55, Amsterdam: North-Holland, pp. 179–181,
822:
may be used to replace the nodes of a cycle or the interior nodes of a path, while fragment
2416:
2383:
2350:
2302:
2248:
2219:
2185:
2149:
2113:
2096:
2057:
2000:
1971:
1934:
1897:
1860:
1823:
1790:
1767:
1744:
1708:
1663:
1636:
1616:
1583:
1556:
1513:
1331:
878:
657:
89:
854:; a graph of this type is planar if and only if it does not contain any fragments of type
720:
examples, together with three infinite families of cubic graphs with lesser connectivity.
8:
1624:
870:
421:
152:
In the original paper defining well-covered graphs, these definitions were restricted to
1667:
1488:, Lecture Notes in Computer Science, vol. 108, Berlin: Springer, pp. 108–123,
2223:
2157:
2121:
2074:
2045:
2004:
1943:
1906:
1869:
1832:
1653:
1565:
874:
184:
62:
26:
2211:
2140:
1851:
560:
vertices, without isolated vertices, the size of a maximum independent set is at most
2198:
Raghavan, Vijay; Spinrad, Jeremy (2003), "Robust algorithms for restricted domains",
2008:
1735:
1499:
940:
785:
2227:
912:
Testing whether a graph contains two maximal independent sets of different sizes is
834:, so the result of performing this replacement process on a path and using fragment
2402:
2369:
2338:
2290:
2207:
2173:
2135:
2084:
2037:
1988:
1957:
1920:
1883:
1846:
1809:
1730:
1694:
1671:
1604:
1592:
1489:
1480:(1981), "Some common properties for regularizable graphs, edge-critical graphs and
963:
951:
858:. The other family is formed by replacing the nodes of a path by fragments of type
778:
740:
736:
590:
575:
525:
417:
109:
46:
2177:
788:) that are well-covered. Four of the graphs (the two prisms, the DĂĽrer graph, and
2412:
2379:
2346:
2298:
2244:
2215:
2181:
2145:
2109:
2092:
2053:
1996:
1967:
1930:
1893:
1856:
1819:
1786:
1763:
1740:
1704:
1632:
1612:
1579:
1552:
1509:
967:
924:
882:
782:
701:
432:
425:
93:
85:
77:
54:
2088:
1536:
724:
445:
405:
176:
161:
120:
in a graph is a set of vertices no two of which are adjacent to each other. If
69:
2065:
Holroyd, Fred; Talbot, John (2005), "Graphs with the Erdős-Ko-Rado property",
1962:
1925:
1888:
1752:
Finbow, A. S.; Hartnell, B. L. (1983), "A game related to covering by stars",
744:
2428:
2268:
1716:
1494:
748:
713:
409:
97:
2407:
2374:
2342:
2324:
2294:
1814:
1608:
1540:
1477:
774:
501:
436:
50:
38:
704:, one of four well-covered 4-connected 3-dimensional simplicial polyhedra.
2189:
913:
886:
709:
401:
81:
2358:
Tankus, David; Tarsi, Michael (1996), "Well-covered claw-free graphs",
2049:
1992:
955:
440:
61:
have equal size. Well-covered graphs were defined and first studied by
1675:
943:, may also be solved in polynomial time for very well covered graphs.
2079:
531:
172:
from the graph produces a graph with a smaller minimum vertex cover.
21:
2041:
688:
680:
668:
is acyclic) then it is well-covered if and only if every vertex of
49:
in which the minimal vertex covers all have the same size. Here, a
1658:
1406:
716:) well-covered graphs have been classified: they consist of seven
696:
96:, but testing whether other kinds of graph are well-covered is a
30:
2314:, Ph.D. thesis, Vanderbilt University, Department of Mathematics
2259:
Well-covered graphs: some new sub-classes and complexity results
1699:
1545:
1525:, Ph.D. thesis, Vanderbilt University, Department of Mathematics
1941:
1904:
1867:
1830:
1356:
1316:
1312:
1308:
480:, each of degree one and each adjacent to a distinct vertex in
1942:
Finbow, Arthur S.; Hartnell, Bert L.; Nowakowski, Richard J.;
1905:
Finbow, Arthur S.; Hartnell, Bert L.; Nowakowski, Richard J.;
1868:
Finbow, Arthur S.; Hartnell, Bert L.; Nowakowski, Richard J.;
1307:
Finbow, Hartnell, and Nowakowski et al. (
609:
is very well covered if and only if it has a perfect matching
759:, an eight-vertex graph obtained from the utility graph by a
1627:; Slater, Peter J. (1993), "A note on well-covered graphs",
1543:(1993), "A characterisation of well-covered cubic graphs",
1279:
1595:; Tarsi, Michael (1996), "Recognizing greedy structures",
919:
In contrast, it is possible to test whether a given graph
2237:
826:
is used to replace the two end nodes of a path. Fragment
412:(a disjoint union of complete graphs) is well-covered. A
1978:
1797:
1774:
1265:
1114:
1065:
723:
The seven 3-connected cubic well-covered graphs are the
164:
for vertex covering in the sense that, for every vertex
140:
is a minimal vertex cover if and only if its complement
53:
is a set of vertices that touches all edges, and it is
2271:(1992), "Complexity results for well-covered graphs",
2266:
2103:
1534:
1456:
1436:
1412:
1400:
1368:
1269:
1089:
636:, then the two endpoints of the path must be adjacent.
1334:
1011:
1009:
644:
is very well covered, then every perfect matching in
484:) is well-covered. For, a maximal independent set in
1095:
664:, the subgraph of vertices within distance three of
1682:
1125:
1040:
1039:For examples of papers using this terminology, see
850:, with at least two of the fragments being of type
1418:
1347:
1328:The graphs constructed in this way are called the
1021:
1006:
994:
532:Bipartiteness, very well covered graphs, and girth
2029:Transactions of the American Mathematical Society
1144:
2426:
1946:(2016), "Well-covered triangulations: Part IV",
954:is maximum; that is, it is equimatchable if its
488:must consist of an arbitrary independent set in
200:
2255:
2197:
1909:(2010), "On well-covered triangulations. III",
1563:
1388:
1285:
1245:
1059:
684:The seven cubic 3-connected well-covered graphs
2262:(Doctoral dissertation), University of Alberta
1872:(2009), "On well-covered triangulations. II",
1751:
1220:
1204:
16:Graph with equal-size maximal independent sets
2064:
1835:(2003), "On well-covered triangulations. I",
1623:
1590:
1376:
1372:
1071:
187:having a simplex for each independent set in
2235:Ravindra, G. (1977), "Well-covered graphs",
2124:(1970), "Some covering concepts in graphs",
2108:, London: Academic Press, pp. 239–254,
958:is well-covered. More strongly it is called
632:is the central edge of a three-edge path in
524:one-vertex cliques. Thus, every graph is an
136:must be an independent set, and vice versa.
2390:
2357:
1444:
1440:
885:, and an irregular polyhedron (a nonconvex
675:
1831:Finbow, A.; Hartnell, B.; Nowakowski, R.;
1523:Some results on planar well-covered graphs
468:with a one-edge graph (that is, the graph
435:is well covered: if one places any set of
2406:
2373:
2312:On some subclasses of well-covered graphs
2284:
2139:
2078:
2015:
1961:
1924:
1887:
1850:
1813:
1734:
1698:
1657:
1643:
1493:
1161:
1159:
1138:
1101:
1044:
660:eight or more (so that, for every vertex
2234:
1520:
1266:Finbow, Hartnell & Nowakowski (1988)
1261:
1241:
1165:
695:
687:
679:
574:is well-covered if and only if it has a
549:
20:
2317:
2309:
2156:
2120:
1715:
1568:(1988), "On well-covered 3-polytopes",
1528:
1460:
1273:
1249:
1237:
1235:
1233:
1224:
1208:
1192:
1188:
1184:
1169:
1137:For the clique cover construction, see
1027:
1015:
1000:
988:
799:
581:with the property that, for every edge
536:
92:allow these graphs to be recognized in
2427:
2323:
1457:Campbell, Ellingham & Royle (1993)
1437:Lesk, Plummer & Pulleyblank (1984)
1424:
1413:Lesk, Plummer & Pulleyblank (1984)
1270:Campbell, Ellingham & Royle (1993)
1180:
1178:
1156:
1113:This class of examples was studied by
1090:Lesk, Plummer & Pulleyblank (1984)
1085:
970:, is well-covered in polynomial time.
773:. Of these graphs, the first four are
2327:(1979), "Randomly matchable graphs",
1476:
1150:
553:
294:
287:
280:
273:
266:
259:
252:
245:
236:
2016:Greenberg, Peter (1993), "Piecewise
1719:(1982), "Very well covered graphs",
1646:SIAM Journal on Discrete Mathematics
1401:Sankaranarayana & Stewart (1992)
1369:Sankaranarayana & Stewart (1992)
1230:
1131:
68:The well-covered graphs include all
2256:Sankaranarayana, Ramesh S. (1994),
1686:Electronic Journal of Combinatorics
1175:
795:) are generalized Petersen graphs.
613:with the following two properties:
13:
496:. More generally, given any graph
144:is a maximal independent set, and
88:, and well-covered graphs of high
14:
2446:
1126:Dochtermann & Engström (2009)
1041:Dochtermann & Engström (2009)
896:-vertex maximal planar graph has
1062:, Section 2.4, "Examples", p. 7.
293:
286:
279:
272:
265:
258:
251:
244:
238:
2394:Journal of Combinatorial Theory
2361:Journal of Combinatorial Theory
2162:"Well-covered graphs: a survey"
2127:Journal of Combinatorial Theory
1801:Journal of Combinatorial Theory
1450:
1430:
1394:
1382:
1362:
1322:
1301:
1291:
1255:
1214:
1198:
1107:
962:if every maximal matching is a
777:. They are the only four cubic
1077:
1033:
982:
927:. To do so, find the subgraph
866:; all such graphs are planar.
103:
1:
2212:10.1016/S0196-6774(03)00048-8
2178:10.1080/16073606.1993.9631737
2141:10.1016/S0021-9800(70)80011-4
1852:10.1016/S0166-218X(03)00393-7
1469:
1389:Raghavan & Spinrad (2003)
1377:Caro, Sebő & Tarsi (1996)
1286:Campbell & Plummer (1988)
1246:Campbell & Plummer (1988)
907:
124:is a vertex cover in a graph
2267:Sankaranarayana, Ramesh S.;
1949:Discrete Applied Mathematics
1912:Discrete Applied Mathematics
1875:Discrete Applied Mathematics
1838:Discrete Applied Mathematics
1736:10.1016/0012-365X(82)90215-1
1221:Finbow & Hartnell (1983)
1205:Finbow & Hartnell (1983)
648:satisfies these properties.
7:
1373:Chvátal & Slater (1993)
1072:Holroyd & Talbot (2005)
194:
29:of the nine diagonals of a
10:
2451:
2089:10.1016/j.disc.2004.08.028
765:generalized Petersen graph
25:A well-covered graph, the
1963:10.1016/j.dam.2016.06.030
1926:10.1016/j.dam.2009.08.002
1889:10.1016/j.dam.2009.03.014
1445:Tankus & Tarsi (1997)
1441:Tankus & Tarsi (1996)
621:belongs to a triangle in
528:of a well-covered graph.
512:into cliques), the graph
74:complete bipartite graphs
2166:Quaestiones Mathematicae
1629:Quo vadis, graph theory?
1521:Campbell, S. R. (1987),
1495:10.1007/3-540-10704-5_10
976:
923:is very well covered in
676:Regularity and planarity
603:complete bipartite graph
460:-vertex graph, then the
414:complete bipartite graph
59:maximal independent sets
2330:Journal of Graph Theory
1693:(2): Research Paper 2,
1139:Cook & Nagel (2010)
1045:Cook & Nagel (2010)
541:very well covered graph
2408:10.1006/jctb.1996.1742
2375:10.1006/jctb.1996.0022
2343:10.1002/jgt.3190030209
2295:10.1002/net.3230220304
1815:10.1006/jctb.1993.1005
1609:10.1006/jagm.1996.0006
1564:Campbell, Stephen R.;
1349:
1060:Sankaranarayana (1994)
946:A graph is said to be
705:
693:
685:
34:
2200:Journal of Algorithms
1981:Period. Math. Hungar.
1597:Journal of Algorithms
1350:
1348:{\displaystyle K_{4}}
699:
691:
683:
108:A vertex cover in an
24:
2310:Staples, J. (1975),
2067:Discrete Mathematics
1722:Discrete Mathematics
1357:Finbow et al. (2016)
1332:
879:pentagonal dipyramid
871:simplicial polyhedra
763:, and the 14-vertex
735:, the graphs of the
593:of the neighbors of
177:independence complex
2158:Plummer, Michael D.
2122:Plummer, Michael D.
1944:Plummer, Michael D.
1907:Plummer, Michael D.
1870:Plummer, Michael D.
1833:Plummer, Michael D.
1668:2010arXiv1003.4447C
1566:Plummer, Michael D.
508:of the vertices of
422:triangle-free graph
1993:10.1007/BF01848079
1345:
1115:Fink et al. (1985)
960:randomly matchable
875:regular octahedron
706:
694:
686:
570:A bipartite graph
185:simplicial complex
158:essential vertices
63:Michael D. Plummer
43:well-covered graph
35:
27:intersection graph
2269:Stewart, Lorna K.
1882:(13): 2799–2817,
1676:10.1137/100818170
1535:Campbell, S. R.;
1505:978-3-540-10704-0
941:Hamiltonian cycle
779:polyhedral graphs
472:formed by adding
426:isolated vertices
392:
391:
2442:
2419:
2410:
2386:
2377:
2353:
2325:Sumner, David P.
2315:
2305:
2288:
2263:
2251:
2230:
2193:
2188:, archived from
2152:
2143:
2116:
2099:
2082:
2073:(1–3): 165–176,
2060:
2025:
2011:
1974:
1965:
1937:
1928:
1900:
1891:
1863:
1854:
1826:
1817:
1793:
1778:Ars Combinatoria
1770:
1755:Ars Combinatoria
1747:
1738:
1729:(2–3): 177–187,
1711:
1702:
1678:
1661:
1639:
1619:
1586:
1571:Ars Combinatoria
1559:
1541:Royle, Gordon F.
1537:Ellingham, M. N.
1526:
1516:
1497:
1483:
1464:
1454:
1448:
1434:
1428:
1422:
1416:
1410:
1404:
1398:
1392:
1386:
1380:
1366:
1360:
1354:
1352:
1351:
1346:
1344:
1343:
1326:
1320:
1305:
1299:
1295:
1289:
1283:
1277:
1259:
1253:
1239:
1228:
1218:
1212:
1202:
1196:
1182:
1173:
1163:
1154:
1148:
1142:
1135:
1129:
1123:
1111:
1105:
1102:Greenberg (1993)
1099:
1093:
1081:
1075:
1069:
1063:
1057:
1048:
1037:
1031:
1025:
1019:
1013:
1004:
998:
992:
986:
964:perfect matching
952:maximal matching
938:
934:
930:
922:
903:
899:
895:
865:
861:
857:
853:
849:
845:
837:
829:
825:
821:
817:
813:
809:
805:
794:
786:convex polyhedra
772:
758:
741:pentagonal prism
737:triangular prism
734:
667:
663:
654:
647:
643:
635:
631:
624:
620:
612:
608:
600:
596:
591:induced subgraph
588:
584:
580:
576:perfect matching
573:
566:
559:
547:
526:induced subgraph
523:
519:
515:
511:
507:
500:together with a
499:
495:
491:
487:
483:
479:
476:new vertices to
475:
471:
467:
459:
455:
418:complement graph
297:
296:
290:
289:
283:
282:
276:
275:
269:
268:
262:
261:
255:
254:
248:
247:
242:
241:
201:
190:
182:
171:
167:
154:connected graphs
147:
143:
139:
135:
127:
123:
110:undirected graph
86:claw-free graphs
47:undirected graph
2450:
2449:
2445:
2444:
2443:
2441:
2440:
2439:
2425:
2424:
2423:
2192:on May 27, 2012
2042:10.2307/2154401
2021:
2017:
1845:(1–3): 97–108,
1625:Chvátal, Václav
1506:
1481:
1472:
1467:
1455:
1451:
1435:
1431:
1423:
1419:
1411:
1407:
1399:
1395:
1387:
1383:
1367:
1363:
1339:
1335:
1333:
1330:
1329:
1327:
1323:
1306:
1302:
1296:
1292:
1284:
1280:
1262:Campbell (1987)
1260:
1256:
1242:Campbell (1987)
1240:
1231:
1219:
1215:
1203:
1199:
1183:
1176:
1166:Ravindra (1977)
1164:
1157:
1149:
1145:
1136:
1132:
1118:
1112:
1108:
1100:
1096:
1082:
1078:
1070:
1066:
1058:
1051:
1038:
1034:
1026:
1022:
1014:
1007:
999:
995:
987:
983:
979:
968:claw-free graph
936:
932:
928:
925:polynomial time
920:
910:
901:
897:
890:
883:snub disphenoid
863:
859:
855:
851:
847:
843:
835:
827:
823:
819:
815:
811:
807:
803:
789:
767:
757:
751:
733:
727:
702:snub disphenoid
678:
665:
661:
652:
645:
641:
633:
629:
622:
618:
610:
606:
598:
594:
586:
582:
578:
571:
561:
557:
550:Ravindra (1977)
545:
534:
521:
517:
513:
509:
505:
497:
493:
489:
485:
481:
477:
473:
469:
465:
457:
453:
398:
397:
396:
299:
298:
291:
284:
277:
270:
263:
256:
249:
239:
197:
188:
180:
169:
165:
145:
141:
137:
133:
125:
121:
118:independent set
106:
94:polynomial time
84:, well-covered
70:complete graphs
17:
12:
11:
5:
2448:
2438:
2437:
2435:Graph families
2422:
2421:
2401:(2): 230–233,
2388:
2368:(2): 293–302,
2355:
2337:(2): 183–186,
2321:
2318:Plummer (1993)
2316:. As cited by
2307:
2286:10.1.1.47.9278
2279:(3): 247–262,
2264:
2253:
2232:
2206:(1): 160–172,
2195:
2172:(3): 253–287,
2154:
2118:
2101:
2062:
2036:(2): 705–720,
2019:
2013:
1987:(4): 287–293,
1976:
1939:
1919:(8): 894–912,
1902:
1865:
1828:
1795:
1772:
1762:(A): 189–198,
1749:
1713:
1680:
1641:
1621:
1603:(1): 137–156,
1588:
1578:(A): 215–242,
1561:
1532:
1529:Plummer (1993)
1527:. As cited by
1518:
1504:
1473:
1471:
1468:
1466:
1465:
1461:Plummer (1993)
1449:
1429:
1417:
1405:
1393:
1381:
1361:
1342:
1338:
1321:
1300:
1290:
1278:
1274:Plummer (1993)
1254:
1250:Plummer (1993)
1229:
1227:, Theorem 4.2.
1225:Plummer (1993)
1213:
1211:, Theorem 4.1.
1209:Plummer (1993)
1197:
1193:Plummer (1993)
1189:Favaron (1982)
1185:Staples (1975)
1174:
1170:Plummer (1993)
1155:
1143:
1130:
1106:
1094:
1076:
1064:
1049:
1032:
1028:Favaron (1982)
1020:
1016:Plummer (1970)
1005:
1001:Plummer (1993)
993:
989:Plummer (1970)
980:
978:
975:
909:
906:
800:Plummer (1993)
755:
731:
725:complete graph
677:
674:
638:
637:
628:If an edge of
626:
537:Favaron (1982)
533:
530:
462:rooted product
446:simple polygon
406:complete graph
393:
390:
389:
387:
384:
381:
378:
375:
372:
369:
366:
363:
360:
359:
356:
352:
351:
348:
344:
343:
340:
336:
335:
332:
328:
327:
324:
320:
319:
316:
312:
311:
308:
304:
303:
300:
292:
285:
278:
271:
264:
257:
250:
243:
237:
235:
231:
230:
228:
225:
222:
219:
216:
213:
210:
207:
204:
199:
198:
196:
193:
162:critical graph
105:
102:
15:
9:
6:
4:
3:
2:
2447:
2436:
2433:
2432:
2430:
2418:
2414:
2409:
2404:
2400:
2396:
2395:
2389:
2385:
2381:
2376:
2371:
2367:
2363:
2362:
2356:
2352:
2348:
2344:
2340:
2336:
2332:
2331:
2326:
2322:
2319:
2313:
2308:
2304:
2300:
2296:
2292:
2287:
2282:
2278:
2274:
2270:
2265:
2261:
2260:
2254:
2250:
2246:
2242:
2238:
2233:
2229:
2225:
2221:
2217:
2213:
2209:
2205:
2201:
2196:
2191:
2187:
2183:
2179:
2175:
2171:
2167:
2163:
2159:
2155:
2151:
2147:
2142:
2137:
2133:
2129:
2128:
2123:
2119:
2115:
2111:
2107:
2102:
2098:
2094:
2090:
2086:
2081:
2076:
2072:
2068:
2063:
2059:
2055:
2051:
2047:
2043:
2039:
2035:
2031:
2030:
2024:
2014:
2010:
2006:
2002:
1998:
1994:
1990:
1986:
1982:
1977:
1973:
1969:
1964:
1959:
1955:
1951:
1950:
1945:
1940:
1936:
1932:
1927:
1922:
1918:
1914:
1913:
1908:
1903:
1899:
1895:
1890:
1885:
1881:
1877:
1876:
1871:
1866:
1862:
1858:
1853:
1848:
1844:
1840:
1839:
1834:
1829:
1825:
1821:
1816:
1811:
1807:
1803:
1802:
1796:
1792:
1788:
1784:
1780:
1779:
1773:
1769:
1765:
1761:
1757:
1756:
1750:
1746:
1742:
1737:
1732:
1728:
1724:
1723:
1718:
1714:
1710:
1706:
1701:
1696:
1692:
1688:
1687:
1681:
1677:
1673:
1669:
1665:
1660:
1655:
1651:
1647:
1642:
1638:
1634:
1630:
1626:
1622:
1618:
1614:
1610:
1606:
1602:
1598:
1594:
1589:
1585:
1581:
1577:
1573:
1572:
1567:
1562:
1558:
1554:
1550:
1546:
1542:
1538:
1533:
1530:
1524:
1519:
1515:
1511:
1507:
1501:
1496:
1491:
1487:
1479:
1478:Berge, Claude
1475:
1474:
1462:
1458:
1453:
1446:
1442:
1438:
1433:
1426:
1425:Sumner (1979)
1421:
1414:
1409:
1402:
1397:
1390:
1385:
1378:
1374:
1370:
1365:
1358:
1340:
1336:
1325:
1318:
1314:
1310:
1304:
1294:
1287:
1282:
1275:
1271:
1267:
1263:
1258:
1251:
1247:
1243:
1238:
1236:
1234:
1226:
1222:
1217:
1210:
1206:
1201:
1194:
1190:
1186:
1181:
1179:
1171:
1167:
1162:
1160:
1152:
1147:
1140:
1134:
1127:
1121:
1116:
1110:
1103:
1098:
1091:
1087:
1086:Sumner (1979)
1080:
1073:
1068:
1061:
1056:
1054:
1046:
1042:
1036:
1029:
1024:
1017:
1012:
1010:
1002:
997:
990:
985:
981:
974:
971:
969:
965:
961:
957:
953:
949:
948:equimatchable
944:
942:
926:
917:
915:
905:
894:
888:
884:
880:
876:
872:
867:
840:
833:
801:
796:
792:
787:
784:
780:
776:
775:planar graphs
770:
766:
762:
761:Y-Δ transform
754:
750:
749:utility graph
746:
742:
738:
730:
726:
721:
719:
715:
711:
703:
698:
690:
682:
673:
671:
659:
649:
640:Moreover, if
627:
616:
615:
614:
604:
592:
577:
568:
564:
555:
551:
542:
538:
529:
527:
504:(a partition
503:
463:
450:
447:
442:
438:
434:
429:
427:
423:
419:
415:
411:
410:cluster graph
407:
403:
388:
385:
382:
379:
376:
373:
370:
367:
364:
362:
361:
357:
354:
353:
349:
346:
345:
341:
338:
337:
333:
330:
329:
325:
322:
321:
317:
314:
313:
309:
306:
305:
301:
233:
232:
229:
226:
223:
220:
217:
214:
211:
208:
205:
203:
202:
192:
186:
178:
173:
163:
159:
155:
150:
131:
119:
114:
111:
101:
99:
98:coNP-complete
95:
91:
87:
83:
79:
78:rook's graphs
75:
71:
66:
64:
60:
56:
52:
48:
44:
40:
32:
28:
23:
19:
2398:
2397:, Series B,
2392:
2365:
2364:, Series B,
2359:
2334:
2328:
2311:
2276:
2272:
2258:
2243:(1): 20–21,
2240:
2236:
2203:
2199:
2190:the original
2169:
2165:
2131:
2125:
2105:
2080:math/0307073
2070:
2066:
2033:
2027:
2022:
1984:
1980:
1953:
1947:
1916:
1910:
1879:
1873:
1842:
1836:
1808:(1): 44–68,
1805:
1804:, Series B,
1799:
1782:
1776:
1759:
1753:
1726:
1720:
1690:
1684:
1649:
1645:
1628:
1600:
1596:
1593:Sebő, András
1591:Caro, Yair;
1575:
1569:
1548:
1544:
1522:
1485:
1452:
1432:
1420:
1408:
1396:
1384:
1364:
1324:
1303:
1293:
1281:
1257:
1216:
1200:
1151:Berge (1981)
1146:
1133:
1119:
1109:
1097:
1079:
1067:
1035:
1023:
996:
984:
972:
959:
947:
945:
918:
911:
892:
868:
841:
814:. Fragments
797:
790:
768:
752:
728:
722:
707:
650:
639:
569:
562:
554:Berge (1981)
540:
535:
520:consists of
502:clique cover
451:
433:rook's graph
430:
399:
174:
157:
151:
115:
107:
82:cubic graphs
67:
51:vertex cover
42:
39:graph theory
36:
18:
2026:geometry",
1785:(A): 5–10,
1717:Favaron, O.
1700:10.37236/68
1551:: 193–212,
1355:-family by
914:NP-complete
887:deltahedron
830:contains a
781:(graphs of
745:DĂĽrer graph
718:3-connected
617:No edge of
402:cycle graph
179:of a graph
168:, deleting
104:Definitions
72:, balanced
1652:: 89–101,
1484:-graphs",
1470:References
956:line graph
908:Complexity
539:defines a
441:chessboard
130:complement
76:, and the
2281:CiteSeerX
2134:: 91–98,
2009:121734811
1956:: 71–94,
1659:1003.4447
950:if every
714:3-regular
100:problem.
65:in 1970.
2429:Category
2273:Networks
2228:16327087
2160:(1993),
739:and the
601:forms a
424:with no
195:Examples
2417:1438624
2384:1376052
2351:0530304
2303:1161178
2249:0469831
2220:2006100
2186:1254158
2150:0289347
2114:0777180
2097:2136060
2058:1140914
2050:2154401
2001:0833264
1972:3548980
1935:2602814
1898:2537505
1861:2024267
1824:1198396
1791:0942485
1768:0737090
1745:0677051
1709:2515765
1664:Bibcode
1637:1217991
1617:1368720
1584:0942505
1557:1220613
1514:0622929
1298:graphs.
802:labels
456:is any
183:is the
55:minimal
31:hexagon
2415:
2382:
2349:
2301:
2283:
2247:
2226:
2218:
2184:
2148:
2112:
2095:
2056:
2048:
2007:
1999:
1970:
1933:
1896:
1859:
1822:
1789:
1766:
1743:
1707:
1635:
1615:
1582:
1555:
1512:
1502:
881:, the
877:, the
832:bridge
810:, and
783:simple
747:, the
743:, the
670:degree
589:, the
128:, the
45:is an
2224:S2CID
2075:arXiv
2046:JSTOR
2005:S2CID
1654:arXiv
977:Notes
793:(7,2)
771:(7,2)
710:cubic
658:girth
625:, and
439:on a
437:rooks
420:of a
90:girth
1500:ISBN
1317:2010
1313:2009
1309:2003
1088:and
1043:and
862:and
846:and
708:The
700:The
597:and
552:and
175:The
41:, a
2403:doi
2370:doi
2339:doi
2291:doi
2208:doi
2174:doi
2136:doi
2085:doi
2071:293
2038:doi
2034:335
1989:doi
1958:doi
1954:215
1921:doi
1917:158
1884:doi
1880:157
1847:doi
1843:132
1810:doi
1731:doi
1695:doi
1672:doi
1605:doi
1490:doi
931:of
818:or
756:3,3
585:in
464:of
452:If
132:of
116:An
37:In
2431::
2413:MR
2411:,
2399:69
2380:MR
2378:,
2366:66
2347:MR
2345:,
2333:,
2299:MR
2297:,
2289:,
2277:22
2275:,
2245:MR
2239:,
2222:,
2216:MR
2214:,
2204:48
2202:,
2182:MR
2180:,
2170:16
2168:,
2164:,
2146:MR
2144:,
2130:,
2110:MR
2093:MR
2091:,
2083:,
2069:,
2054:MR
2052:,
2044:,
2032:,
2018:SL
2003:,
1997:MR
1995:,
1985:16
1983:,
1968:MR
1966:,
1952:,
1931:MR
1929:,
1915:,
1894:MR
1892:,
1878:,
1857:MR
1855:,
1841:,
1820:MR
1818:,
1806:57
1787:MR
1783:25
1781:,
1764:MR
1760:16
1758:,
1741:MR
1739:,
1727:42
1725:,
1705:MR
1703:,
1691:16
1689:,
1670:,
1662:,
1650:26
1648:,
1633:MR
1613:MR
1611:,
1601:20
1599:,
1580:MR
1576:25
1574:,
1553:MR
1549:13
1547:,
1539:;
1510:MR
1508:,
1498:,
1459:;
1443:;
1439:;
1375:;
1371:;
1319:).
1315:,
1311:,
1272:;
1268:;
1264:;
1248:;
1244:;
1232:^
1223:;
1207:;
1191:;
1187:;
1177:^
1168:;
1158:^
1122:/2
1052:^
1008:^
806:,
583:uv
565:/2
431:A
400:A
2420:.
2405::
2387:.
2372::
2354:.
2341::
2335:3
2320:.
2306:.
2293::
2252:.
2241:2
2231:.
2210::
2194:.
2176::
2153:.
2138::
2132:8
2117:.
2100:.
2087::
2077::
2061:.
2040::
2023:Z
2020:2
2012:.
1991::
1975:.
1960::
1938:.
1923::
1901:.
1886::
1864:.
1849::
1827:.
1812::
1794:.
1771:.
1748:.
1733::
1712:.
1697::
1679:.
1674::
1666::
1656::
1640:.
1620:.
1607::
1587:.
1560:.
1531:.
1517:.
1492::
1482:B
1463:.
1447:.
1427:.
1415:.
1403:.
1391:.
1379:.
1341:4
1337:K
1288:.
1276:.
1252:.
1195:.
1172:.
1153:.
1128:.
1120:n
1104:.
1092:.
1074:.
1047:.
1030:.
1018:.
1003:.
937:H
933:G
929:H
921:G
902:t
898:t
893:t
891:3
864:C
860:B
856:B
852:A
848:B
844:A
836:A
828:A
824:C
820:B
816:A
812:C
808:B
804:A
791:G
769:G
753:K
732:4
729:K
712:(
666:v
662:v
653:G
646:G
642:G
634:G
630:M
623:G
619:M
611:M
607:G
599:v
595:u
587:M
579:M
572:G
563:n
558:n
546:G
522:n
518:p
514:G
510:G
506:p
498:G
494:n
490:G
486:H
482:G
478:G
474:n
470:H
466:G
458:n
454:G
386:h
383:g
380:f
377:e
374:d
371:c
368:b
365:a
358:1
355:1
350:2
347:2
342:3
339:3
334:4
331:4
326:5
323:5
318:6
315:6
310:7
307:7
302:8
234:8
227:h
224:g
221:f
218:e
215:d
212:c
209:b
206:a
189:G
181:G
170:v
166:v
146:C
142:I
138:C
134:C
126:G
122:C
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
