20:
559:. That is, there exists a set of edges in the graph such that each vertex is an endpoint of exactly one of the matched edges. The special case of this result for line graphs implies that, in any graph with an even number of edges, one can partition the edges into paths of length two. Perfect matchings may be used to provide another characterization of the claw-free graphs: they are exactly the graphs in which every connected induced subgraph of even order has a perfect matching.
727:
525:
848:). However, for many years this remained an unsolved conjecture, only proven for special subclasses of graphs. One of these subclasses was the family of claw-free graphs: it was discovered by several authors that claw-free graphs without odd cycles and odd holes are perfect. Perfect claw-free graphs may be recognized in polynomial time. In a perfect claw-free graph, the neighborhood of any vertex forms the complement of a
116:
998:
for minor-closed graph families proven by
Robertson and Seymour, and to the structure theory for perfect graphs that Chudnovsky, Seymour and their co-authors used to prove the strong perfect graph theorem. The theory is too complex to describe in detail here, but to give a flavor of it, it suffices
914:
contains a large clique, of size roughly proportional to the square root of the degree. For connected claw-free graphs that include at least one three-vertex independent set, a stronger relation between chromatic number and clique size is possible: in these graphs, there exists a clique of size at
978:
Despite this domination perfectness property, it is NP-hard to determine the size of the minimum dominating set in a claw-free graph. However, in contrast to the situation for more general classes of graphs, finding the minimum dominating set or the minimum connected dominating set in a claw-free
399:
the neighbors of the vertex would not have enough remaining edges to form the complement of a triangle-free graph. This observation allows the check of each neighborhood in the fast matrix multiplication based algorithm outlined above to be performed in the same asymptotic time bound as
1018:. This generalizes the construction of a line graph, in which every edge of the multigraph is replaced by a vertex. Fuzzy linear interval graphs are constructed in the same way as fuzzy circular interval graphs, but on a line rather than on a circle.
812:, Minty's result may also be used to solve in polynomial time the more general problem of finding in claw-free graphs an independent set of maximum weight. Generalizations of these results to wider classes of graphs are also known. By showing a novel
228:
must share one of those endpoints with each other. Line graphs may be characterized in terms of nine forbidden subgraphs; the claw is the simplest of these nine graphs. This characterization provided the initial motivation for studying claw-free
875:
In general, it is NP-hard to find the largest clique in a claw-free graph. It is also NP-hard to find an optimal coloring of the graph, because (via line graphs) this problem generalizes the NP-hard problem of computing the
349:), by testing each 4-tuple of vertices to determine whether they induce a claw. With more efficiency, and greater complication, one can test whether a graph is claw-free by checking, for each vertex of the graph, that the
562:
Sumner's proof shows, more strongly, that in any connected claw-free graph one can find a pair of adjacent vertices the removal of which leaves the remaining graph connected. To show this, Sumner finds a pair of vertices
258:
of families of intervals in which no interval contains another interval, are claw-free, because four properly intersecting intervals cannot intersect in the pattern of a claw. The same is true more generally for proper
966:
can be replaced by one of the undominated vertices in its clique producing a dominating set with fewer adjacencies. By repeating this replacement process one eventually reaches a dominating set no larger than
797:
with any augmenting path gives a larger independent set, the task thus reduces to searching for augmenting paths until no more can be found, analogously as in algorithms for finding maximum matchings.
1026:
Six specific subclasses of claw-free graphs. Three of these are line graphs, proper circular arc graphs, and the induced subgraphs of an icosahedron; the other three involve additional definitions.
808:
step. Minty's approach is to transform the problem instance into an auxiliary line graph and use
Edmonds' algorithm directly to find the augmenting paths. After a correction by
1665:
Faenza, Yuri; Oriolo, Gianpaolo; Stauffer, Gautier (2011), "An
Algorithmic Decomposition of Claw-free Graphs Leading to an O(n)-algorithm for the Weighted Stable Set Problem",
1574:
Cygan, Marek; Philip, Geevarghese; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry (2011), "Dominating set is fixed parameter tractable in claw-free graphs",
64:
is a claw; i.e., any subset of four vertices has other than only three edges connecting them in this pattern. Equivalently, a claw-free graph is a graph in which the
1342:
Chrobak, Marek; Naor, Joseph; Novick, Mark B. (1989), "Using bounded degree spanning trees in the design of efficient algorithms on claw-free graphs", in Dehne, F.;
1860:
844:) that perfect graphs may be characterized as the graphs that do not have as induced subgraphs either an odd cycle or the complement of an odd cycle (a so-called
1055:
and new bounds on the chromatic number of claw-free graphs, as well as to new fixed-parameter-tractable algorithms for dominating sets in claw-free graphs.
603:
leaves the remaining graph connected. Repeatedly removing matched pairs of vertices in this way forms a perfect matching in the given claw-free graph.
497:
479:
1348:
869:
1576:
983:: it can be solved in time bounded by a polynomial in the size of the graph multiplied by an exponential function of the dominating set size.
698: ≥ 2; claw-free graphs of odd order with at most one degree-one vertex may be partitioned into an odd cycle and a matching; for any
1837:
1687:
1375:
2063:
926:
that is independent, and if the same property holds in all of its induced subgraphs. Claw-free graphs have this property. To see this, let
765:
Both approaches use the observation that in claw-free graphs, no vertex can have more than two neighbors in an independent set, and so the
1812:
Automata, Languages and
Programming: 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I
1051:
with parameters srg(27,16,10,8), plays an important role in this part of the analysis. This structure theory has led to new advances in
373:
769:
of two independent sets must induce a subgraph of degree at most two; that is, it is a union of paths and cycles. In particular, if
918:
Although not every claw-free graph is perfect, claw-free graphs satisfy another property, related to perfection. A graph is called
2231:
1495:
888:
algorithm, because the chromatic number of a claw-free graph is greater than half its maximum degree. A generalization of the
1777:
1710:
1389:
735:
738:
in a line graph corresponds to a matching in its underlying graph, a set of edges no two of which share an endpoint. The
1530:
1483:
1452:
1397:
1393:
841:
528:
Sumner's proof that claw-free connected graphs of even order have perfect matchings: removing the two adjacent vertices
906:, meaning that every claw-free graph of large chromatic number contains a large clique. More strongly, it follows from
418:
matrix multiplication, or faster for vertices with even lower degrees. The worst case for this algorithm occurs when Ω(
271:
1011:, a class of graphs represented geometrically by points and arcs on a circle, generalizing proper circular arc graphs.
65:
954:
would be the center of a claw). If every vertex in this clique is already dominated by at least one other member of
1901:
1871:
361:
contains a nonzero diagonal element, so finding a triangle may be performed in the same asymptotic time bound as
73:
2113:
Sbihi, Najiba (1980), "Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile",
1943:
Kloks, Ton; Kratsch, Dieter; MĂĽller, Haiko (2000), "Finding and counting small induced subgraphs efficiently",
1052:
980:
919:
47:
2226:
1343:
1233:
995:
751:
100:
773:
is a non-maximum independent set, it differs from any maximum independent set by even cycles and so called
1542:
1466:, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge: Cambridge Univ. Press, pp. 153–171,
1232:
observe on p. 132 that the NP-hardness of cliques in claw-free graphs follows from the NP-hardness of the
1048:
994:
overview a series of papers in which they prove a structure theory for claw-free graphs, analogous to the
325:
456:
vertices grows at least as quickly as the number of triangle-free graphs, exponentially in the square of
87:, and gained additional motivation through three key discoveries about them: the fact that all claw-free
1409:
911:
452:
Because claw-free graphs include complements of triangle-free graphs, the number of claw-free graphs on
369:
247:
69:
1039:
defined as the claw-free graphs in which every four vertices induce a subgraph with at least two edges.
396:
1332:
Beineke, L. W. (1968), "Derived graphs of digraphs", in Sachs, H.; Voss, H.-J.; Walter, H.-J. (eds.),
60:
comprising three edges, three leaves, and a central vertex). A claw-free graph is a graph in which no
1807:
766:
655:
306:
204:
1547:
1043:
Much of the work in their structure theory involves a further analysis of antiprismatic graphs. The
1003:(equivalently, locally co-bipartite graphs), they state that every such graph has one of two forms:
1237:
999:
to outline two of their results. First, for a special subclass of claw-free graphs which they call
907:
881:
651:
237:
77:
36:
2164:
1972:
1931:
1913:
1843:
1815:
1763:
1741:
1693:
1653:
1611:
1585:
1436:
1418:
754:
in line graphs. This has been independently extended to an algorithm for all claw-free graphs by
671:
667:
260:
255:
2029:"A revision of Minty's algorithm for finding a maximum weighted stable set of a claw-free graph"
1775:
Gravier, Sylvain; Maffray, Frédéric (2004), "On the choice number of claw-free perfect graphs",
1022:
Chudnovsky and
Seymour classify arbitrary connected claw-free graphs into one of the following:
19:
2028:
840:
are equal, and in which this equality persists in every induced subgraph. It is now known (the
2199:
1854:
1833:
1683:
1371:
1044:
889:
801:
739:
513:
486:
If the graphs are allowed to be disconnected, the numbers of graphs are even larger: they are
321:
302:
1666:
353:
of its neighbors does not contain a triangle. A graph contains a triangle if and only if the
2156:
2122:
2072:
2040:
2005:
1952:
1923:
1880:
1825:
1814:, Lecture Notes in Computer Science, vol. 6755, Zurich, Switzerland, pp. 462–473,
1786:
1755:
1719:
1675:
1635:
1595:
1552:
1526:
1504:
1479:
1448:
1428:
1385:
1361:
1353:
975:
is a minimum dominating set this process forms an equally small independent dominating set.
833:
747:
556:
358:
350:
233:
92:
61:
40:
2176:
2136:
2105:
2084:
2019:
1988:
1964:
1892:
1798:
1733:
1649:
1607:
1566:
1518:
1471:
1456:
1349:
Algorithms and Data
Structures: Workshop WADS '89, Ottawa, Canada, August 1989, Proceedings
726:
524:
2172:
2132:
2101:
2080:
2015:
1984:
1960:
1888:
1794:
1729:
1645:
1603:
1562:
1514:
1467:
896:
equals the chromatic number; these two numbers can be far apart in other kinds of graphs.
885:
877:
849:
552:
96:
88:
1996:
Minty, George J. (1980), "On maximal independent sets of vertices in claw-free graphs",
436:) neighbors each, and the remaining vertices have few neighbors, so its total time is O(
107:. They are the subject of hundreds of mathematical research papers and several surveys.
1904:(2015), "Claw-free graphs, skeletal graphs, and a stronger conjecture on ω, Δ, and χ",
923:
853:
837:
354:
309:
formed by removing a perfect matching from a complete graph), the graph of the regular
298:
251:
241:
1956:
1790:
1724:
866:
Do claw-free graphs always have list chromatic number equal to their chromatic number?
119:
The regular icosahedron, a polyhedron whose vertices and edges form a claw-free graph.
2220:
2127:
2010:
1746:
1705:
1440:
1401:
893:
829:
267:
104:
2203:
1767:
1697:
1657:
1615:
1352:, Lecture Notes in Comput. Sci., vol. 382, Berlin: Springer, pp. 147–162,
2144:
2055:
1935:
1847:
1623:
880:
of a graph. For the same reason, it is NP-hard to find a coloring that achieves an
778:
540:
leaves a connected subgraph, within which the same removal process may be repeated.
28:
900:
856:
perfect claw-free graphs, or to find maximum cliques in them, in polynomial time.
1829:
1668:
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on
Discrete Algorithms
1036:
509:
310:
286:
1679:
1557:
1509:
1432:
2076:
1599:
294:
278:
125:
84:
57:
2190:
1487:
1357:
962:
can be removed producing a smaller independent dominating set, and otherwise
884:
better than 4/3. However, an approximation ratio of two can be achieved by a
702:
that is at most half the minimum degree of a claw-free graph in which either
642:. Therefore, the process of forming a matching by finding and removing pairs
2208:
1708:; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey",
2092:
Poljak, Svatopluk (1974), "A note on stable sets and colorings of graphs",
1869:
Itai, Alon; Rodeh, Michael (1978), "Finding a minimum circuit in a graph",
1744:; Karzanov, Alexander V. (1996), "Path problems in skew-symmetric graphs",
1640:
730:
A non-maximum independent set (the two violet nodes) and an augmenting path
2045:
282:
115:
2168:
1759:
858:
820:
gave a cubic time algorithm, which also works in the weighted setting.
314:
290:
1927:
1423:
1366:
804:
step of
Edmonds' algorithm and adds a similar, but more complicated,
376:, the total time for this claw-free recognition algorithm would be O(
2160:
1884:
750:
in any graph in polynomial time, which is equivalent to computing a
1918:
1820:
1590:
1014:
A graph constructed from a multigraph by replacing each edge by a
1316:
1292:
472:
1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, ... (sequence
1205:
1029:
Graphs formed in four simple ways from smaller claw-free graphs.
2054:
Palmer, Edgar M.; Read, Ronald C.; Robinson, Robert W. (2002),
1674:, SODA '11, San Francisco, California: SIAM, pp. 630–646,
638:
from the graph does not change any of the other distances from
83:
Claw-free graphs were initially studied as a generalization of
386:
observe that in any claw-free graph, each vertex has at most 2
1288:
270:, a seven-vertex graph used to provide a lower bound for the
571:
that are as far apart as possible in the graph, and chooses
930:
be a dominating set in a claw-free graph, and suppose that
492:
474:
103:
in claw-free graphs, and the characterization of claw-free
694:-free graphs of even order have perfect matchings for any
1806:
Hermelin, Danny; Mnich, Matthias; van
Leeuwen, Erik Jan;
789:, and for which both endpoints have only one neighbor in
240:
is claw-free. These graphs include as a special case any
680:
list several related results, including the following: (
337:
It is straightforward to verify that a given graph with
159:) whenever the corresponding edges share an endpoint in
1977:
Cahiers du Centre d'Études de
Recherche Opérationnelle
1276:
1229:
1217:
1190:
1175:
1148:
1102:
1075:
718:-edge matching can be extended to a perfect matching.
677:
666:
provide an alternative linear-time algorithm based on
817:
591:
can lie on any shortest path from any other node to
490:
1, 2, 4, 10, 26, 85, 302, 1285, 6170, ... (sequence
2094:
Commentationes Mathematicae Universitatis Carolinae
2033:
Journal of the Operations Research Society of Japan
706:or the number of vertices is even, the graph has a
505:
383:
1488:"Claw-free graphs. III. Circular interval graphs"
1264:
1131:
1114:
991:
663:
2149:Proceedings of the American Mathematical Society
171:) cannot contain a claw, because if three edges
460:. The numbers of connected claw-free graphs on
2193:, Information System on Graph Class Inclusions
1252:
809:
512:to be counted very efficiently, unusually for
1810:(2011), "Domination when the stars are out",
8:
606:The same proof idea holds more generally if
2027:Nakamura, Daishin; Tamura, Akihisa (2001),
548:
2155:(1), American Mathematical Society: 8–12,
1859:: CS1 maint: location missing publisher (
1533:(2010), "Claw-free graphs VI. Colouring",
1201:
1199:
285:are claw-free, including the graph of the
2126:
2044:
2009:
1998:Journal of Combinatorial Theory, Series B
1975:(1975), "A note on matchings in graphs",
1917:
1819:
1723:
1639:
1589:
1556:
1546:
1508:
1422:
1365:
1160:
971:, so in particular when the starting set
614:is any vertex that is maximally far from
1304:
1144:
1142:
1140:
942:; then the set of vertices dominated by
781:which alternate between vertices not in
725:
710:-factor; and, if a claw-free graph is (2
523:
114:
18:
16:Graph without four-vertex star subgraphs
1171:
1169:
1098:
1096:
1087:
1071:
1069:
1067:
1063:
892:states that, for claw-free graphs, the
870:(more unsolved problems in mathematics)
743:
1852:
1277:Faudree, Flandrin & Ryjáček (1997)
1241:
1230:Faudree, Flandrin & Ryjáček (1997)
1218:Faudree, Flandrin & Ryjáček (1997)
1191:Faudree, Flandrin & Ryjáček (1997)
1186:
1184:
1176:Faudree, Flandrin & Ryjáček (1997)
1149:Faudree, Flandrin & Ryjáček (1997)
1127:
1125:
1123:
1103:Faudree, Flandrin & Ryjáček (1997)
1076:Faudree, Flandrin & Ryjáček (1997)
678:Faudree, Flandrin & Ryjáček (1997)
555:with an even number of vertices has a
544:
196:all share endpoints with another edge
759:
755:
468: = 1, 2, ... are
293:(a complete graph), the graph of the
7:
2064:SIAM Journal on Discrete Mathematics
1626:(1965), "Paths, Trees and Flowers",
910:that every claw-free graph of large
818:Faenza, Oriolo & Stauffer (2011)
714: + 1)-connected, then any
1457:"The structure of claw-free graphs"
1402:"The strong perfect graph theorem"
1336:, Leipzig: Teubner, pp. 17–33
583:as possible; as he shows, neither
506:Palmer, Read & Robinson (2002)
384:Kloks, Kratsch & MĂĽller (2000)
14:
2147:(1974), "Graphs with 1-factors",
2056:"Counting claw-free cubic graphs"
915:least half the chromatic number.
824:Coloring, cliques, and domination
793:. As the symmetric difference of
664:Chrobak, Naor & Novick (1989)
147:) has a vertex for every edge of
800:Sbihi's algorithm recreates the
684: − 1)-connected
35:is a graph that does not have a
1628:Canadian Journal of Mathematics
1535:Journal of Combinatorial Theory
1496:Journal of Combinatorial Theory
1265:Chudnovsky & Seymour (2010)
1132:Chudnovsky & Seymour (2005)
1115:Chudnovsky & Seymour (2008)
992:Chudnovsky & Seymour (2005)
861:Unsolved problem in mathematics
508:allows the number of claw-free
328:with 27 vertices, is claw-free.
151:, and vertices are adjacent in
46:A claw is another name for the
1945:Information Processing Letters
813:
374:Coppersmith–Winograd algorithm
1:
1957:10.1016/S0020-0190(00)00047-8
1791:10.1016/S0012-365X(03)00292-9
1725:10.1016/S0012-365X(96)00045-3
1464:Surveys in combinatorics 2005
1009:fuzzy circular interval graph
938:are two adjacent vertices in
890:edge list coloring conjecture
658:tree of the graph, rooted at
650:may be performed by a single
345:edges is claw-free in time O(
272:chromatic number of the plane
2128:10.1016/0012-365X(90)90287-R
2011:10.1016/0095-8956(80)90074-X
1830:10.1007/978-3-642-22006-7_39
1577:Theoretical Computer Science
1253:Gravier & Maffray (2004)
842:strong perfect graph theorem
646:that are maximally far from
551:proved that every claw-free
395:neighbors; for otherwise by
31:, an area of mathematics, a
1334:Beiträge zur Graphentheorie
1016:fuzzy linear interval graph
626:that is maximally far from
2248:
1680:10.1137/1.9781611973082.49
1558:10.1016/j.jctb.2010.04.005
1510:10.1016/j.jctb.2008.03.001
1433:10.4007/annals.2006.164.51
810:Nakamura & Tamura 2001
630:. Further, the removal of
297:and more generally of any
289:and more generally of any
2198:Mugan, Jonathan William;
2077:10.1137/S0895480194274777
1872:SIAM Journal on Computing
1600:10.1016/j.tcs.2011.09.010
981:fixed-parameter tractable
899:The claw-free graphs are
1358:10.1007/3-540-51542-9_13
1206:Chudnovsky et al. (2006)
1053:polyhedral combinatorics
832:is a graph in which the
101:maximum independent sets
48:complete bipartite graph
2232:Matching (graph theory)
1906:Journal of Graph Theory
1234:independent set problem
1161:Itai & Rodeh (1978)
996:graph structure theorem
950:must be a clique (else
752:maximum independent set
670:, as well as efficient
536:that are farthest from
372:. Therefore, using the
313:, and the graph of the
99:algorithms for finding
1641:10.4153/CJM-1965-045-4
1346:; Santoro, N. (eds.),
1317:Hermelin et al. (2011)
1305:King & Reed (2015)
1293:Hermelin et al. (2011)
1049:strongly regular graph
731:
674:for the same problem.
541:
326:strongly regular graph
277:The graphs of several
248:Proper interval graphs
120:
24:
2046:10.15807/jorsj.44.194
1410:Annals of Mathematics
894:list chromatic number
729:
527:
370:matrix multiplication
118:
22:
2115:Discrete Mathematics
1778:Discrete Mathematics
1711:Discrete Mathematics
1240:, proven NP-hard by
1238:triangle-free graphs
1033:Antiprismatic graphs
922:if it has a minimum
852:. It is possible to
836:and the size of the
767:symmetric difference
656:breadth first search
595:, so the removal of
579:that is as far from
575:to be a neighbor of
547:and, independently,
307:cocktail party graph
205:pigeonhole principle
1742:Goldberg, Andrew V.
1289:Cygan et al. (2011)
882:approximation ratio
802:blossom contraction
672:parallel algorithms
652:postorder traversal
622:is any neighbor of
261:circular-arc graphs
256:intersection graphs
238:triangle-free graph
95:, the discovery of
91:of even order have
78:triangle-free graph
2200:Weisstein, Eric W.
1983:(2–3–4): 257–260,
1808:Woeginger, Gerhard
1760:10.1007/BF01261321
920:domination perfect
806:clique contraction
732:
668:depth-first search
662:, in linear time.
549:Las Vergnas (1975)
542:
427:) vertices have Ω(
121:
25:
2204:"Claw-Free Graph"
1928:10.1002/jgt.21797
1900:King, Andrew D.;
1839:978-3-642-22005-0
1689:978-0-89871-993-2
1584:(50): 6982–7000,
1527:Chudnovsky, Maria
1480:Chudnovsky, Maria
1449:Chudnovsky, Maria
1386:Chudnovsky, Maria
1377:978-3-540-51542-5
1001:quasi-line graphs
814:structure theorem
740:blossom algorithm
514:graph enumeration
93:perfect matchings
2239:
2213:
2212:
2191:Claw-free graphs
2179:
2145:Sumner, David P.
2139:
2130:
2108:
2087:
2060:
2049:
2048:
2022:
2013:
1991:
1967:
1951:(3–4): 115–121,
1938:
1921:
1895:
1864:
1858:
1850:
1823:
1801:
1785:(1–3): 211–218,
1770:
1736:
1727:
1700:
1673:
1660:
1643:
1618:
1593:
1569:
1560:
1550:
1521:
1512:
1492:
1474:
1461:
1443:
1426:
1406:
1380:
1369:
1337:
1320:
1314:
1308:
1302:
1296:
1286:
1280:
1274:
1268:
1262:
1256:
1250:
1244:
1227:
1221:
1215:
1209:
1203:
1194:
1188:
1179:
1173:
1164:
1158:
1152:
1146:
1135:
1129:
1118:
1112:
1106:
1100:
1091:
1085:
1079:
1073:
908:Ramsey's theorem
862:
834:chromatic number
785:and vertices in
775:augmenting paths
748:maximum matching
722:Independent sets
557:perfect matching
495:
477:
440:) = O(
435:
434:
426:
425:
417:
416:
408:
407:
394:
393:
359:adjacency matrix
351:complement graph
207:at least two of
89:connected graphs
62:induced subgraph
41:induced subgraph
2247:
2246:
2242:
2241:
2240:
2238:
2237:
2236:
2217:
2216:
2197:
2196:
2187:
2161:10.2307/2039666
2143:
2112:
2091:
2058:
2053:
2026:
1995:
1973:Las Vergnas, M.
1971:
1942:
1899:
1885:10.1137/0207033
1868:
1851:
1840:
1805:
1774:
1740:
1718:(1–3): 87–147,
1704:
1690:
1671:
1664:
1622:
1573:
1548:10.1.1.220.7715
1525:
1490:
1478:
1459:
1447:
1404:
1390:Robertson, Neil
1384:
1378:
1341:
1331:
1328:
1323:
1315:
1311:
1303:
1299:
1287:
1283:
1275:
1271:
1263:
1259:
1251:
1247:
1228:
1224:
1216:
1212:
1204:
1197:
1189:
1182:
1174:
1167:
1159:
1155:
1147:
1138:
1130:
1121:
1113:
1109:
1101:
1094:
1086:
1082:
1074:
1065:
1061:
989:
886:greedy coloring
878:chromatic index
873:
872:
867:
864:
860:
850:bipartite graph
826:
736:independent set
724:
693:
610:is any vertex,
553:connected graph
522:
504:A technique of
491:
473:
450:
430:
428:
421:
419:
412:
410:
403:
401:
397:Turán's theorem
389:
387:
335:
274:, is claw-free.
252:interval graphs
227:
220:
213:
202:
191:
184:
177:
163:. A line graph
135:) of any graph
113:
97:polynomial time
55:
33:claw-free graph
17:
12:
11:
5:
2245:
2243:
2235:
2234:
2229:
2227:Graph families
2219:
2218:
2215:
2214:
2194:
2186:
2185:External links
2183:
2182:
2181:
2141:
2110:
2089:
2051:
2039:(2): 194–204,
2024:
2004:(3): 284–304,
1993:
1969:
1940:
1912:(3): 157–194,
1902:Reed, Bruce A.
1897:
1879:(4): 413–423,
1866:
1838:
1803:
1772:
1754:(3): 353–382,
1738:
1706:Faudree, Ralph
1702:
1688:
1662:
1620:
1571:
1541:(6): 560–572,
1523:
1503:(4): 812–834,
1476:
1445:
1382:
1376:
1339:
1327:
1324:
1322:
1321:
1309:
1297:
1281:
1279:, pp. 124–125.
1269:
1257:
1245:
1222:
1220:, pp. 135–136.
1210:
1195:
1193:, pp. 133–134.
1180:
1178:, pp. 120–124.
1165:
1153:
1136:
1119:
1107:
1092:
1088:Beineke (1968)
1080:
1062:
1060:
1057:
1047:, a claw-free
1045:Schläfli graph
1041:
1040:
1030:
1027:
1020:
1019:
1012:
988:
985:
924:dominating set
912:maximum degree
868:
865:
859:
838:maximum clique
825:
822:
744:Edmonds (1965)
723:
720:
688:
521:
518:
502:
501:
484:
483:
449:
446:
409: Ă— 2
334:
331:
330:
329:
322:Schläfli graph
318:
299:cross polytope
275:
264:
245:
242:complete graph
230:
225:
218:
211:
200:
189:
182:
175:
139:is claw-free;
112:
109:
105:perfect graphs
53:
15:
13:
10:
9:
6:
4:
3:
2:
2244:
2233:
2230:
2228:
2225:
2224:
2222:
2211:
2210:
2205:
2201:
2195:
2192:
2189:
2188:
2184:
2178:
2174:
2170:
2166:
2162:
2158:
2154:
2150:
2146:
2142:
2138:
2134:
2129:
2124:
2120:
2116:
2111:
2107:
2103:
2099:
2095:
2090:
2086:
2082:
2078:
2074:
2070:
2066:
2065:
2057:
2052:
2047:
2042:
2038:
2034:
2030:
2025:
2021:
2017:
2012:
2007:
2003:
1999:
1994:
1990:
1986:
1982:
1978:
1974:
1970:
1966:
1962:
1958:
1954:
1950:
1946:
1941:
1937:
1933:
1929:
1925:
1920:
1915:
1911:
1907:
1903:
1898:
1894:
1890:
1886:
1882:
1878:
1874:
1873:
1867:
1862:
1856:
1849:
1845:
1841:
1835:
1831:
1827:
1822:
1817:
1813:
1809:
1804:
1800:
1796:
1792:
1788:
1784:
1780:
1779:
1773:
1769:
1765:
1761:
1757:
1753:
1749:
1748:
1747:Combinatorica
1743:
1739:
1735:
1731:
1726:
1721:
1717:
1713:
1712:
1707:
1703:
1699:
1695:
1691:
1685:
1681:
1677:
1670:
1669:
1663:
1659:
1655:
1651:
1647:
1642:
1637:
1633:
1629:
1625:
1624:Edmonds, Jack
1621:
1617:
1613:
1609:
1605:
1601:
1597:
1592:
1587:
1583:
1579:
1578:
1572:
1568:
1564:
1559:
1554:
1549:
1544:
1540:
1536:
1532:
1531:Seymour, Paul
1528:
1524:
1520:
1516:
1511:
1506:
1502:
1498:
1497:
1489:
1485:
1484:Seymour, Paul
1481:
1477:
1473:
1469:
1465:
1458:
1454:
1453:Seymour, Paul
1450:
1446:
1442:
1438:
1434:
1430:
1425:
1420:
1417:(1): 51–229,
1416:
1412:
1411:
1403:
1399:
1398:Thomas, Robin
1395:
1394:Seymour, Paul
1391:
1387:
1383:
1379:
1373:
1368:
1363:
1359:
1355:
1351:
1350:
1345:
1340:
1335:
1330:
1329:
1325:
1318:
1313:
1310:
1306:
1301:
1298:
1294:
1290:
1285:
1282:
1278:
1273:
1270:
1266:
1261:
1258:
1254:
1249:
1246:
1243:
1242:Poljak (1974)
1239:
1235:
1231:
1226:
1223:
1219:
1214:
1211:
1207:
1202:
1200:
1196:
1192:
1187:
1185:
1181:
1177:
1172:
1170:
1166:
1162:
1157:
1154:
1150:
1145:
1143:
1141:
1137:
1133:
1128:
1126:
1124:
1120:
1116:
1111:
1108:
1104:
1099:
1097:
1093:
1089:
1084:
1081:
1077:
1072:
1070:
1068:
1064:
1058:
1056:
1054:
1050:
1046:
1038:
1035:, a class of
1034:
1031:
1028:
1025:
1024:
1023:
1017:
1013:
1010:
1006:
1005:
1004:
1002:
997:
993:
986:
984:
982:
976:
974:
970:
965:
961:
957:
953:
949:
945:
941:
937:
933:
929:
925:
921:
916:
913:
909:
905:
903:
897:
895:
891:
887:
883:
879:
871:
857:
855:
851:
847:
843:
839:
835:
831:
830:perfect graph
823:
821:
819:
815:
811:
807:
803:
798:
796:
792:
788:
784:
780:
779:induced paths
776:
772:
768:
763:
761:
757:
753:
749:
745:
741:
737:
728:
721:
719:
717:
713:
709:
705:
701:
697:
692:
687:
683:
679:
675:
673:
669:
665:
661:
657:
653:
649:
645:
641:
637:
633:
629:
625:
621:
617:
613:
609:
604:
602:
598:
594:
590:
586:
582:
578:
574:
570:
566:
560:
558:
554:
550:
546:
545:Sumner (1974)
539:
535:
531:
526:
519:
517:
515:
511:
507:
499:
494:
489:
488:
487:
481:
476:
471:
470:
469:
467:
463:
459:
455:
447:
445:
443:
439:
433:
424:
415:
406:
398:
392:
385:
381:
379:
375:
371:
368:
365: Ă—
364:
360:
356:
352:
348:
344:
341:vertices and
340:
332:
327:
323:
319:
316:
312:
308:
304:
300:
296:
292:
288:
284:
280:
276:
273:
269:
268:Moser spindle
265:
262:
257:
253:
249:
246:
243:
239:
235:
231:
224:
217:
210:
206:
199:
195:
188:
181:
174:
170:
166:
162:
158:
154:
150:
146:
142:
138:
134:
130:
127:
123:
122:
117:
110:
108:
106:
102:
98:
94:
90:
86:
81:
79:
75:
71:
67:
63:
59:
52:
49:
44:
42:
38:
34:
30:
21:
2207:
2152:
2148:
2121:(1): 53–76,
2118:
2114:
2097:
2093:
2071:(1): 65–73,
2068:
2062:
2036:
2032:
2001:
1997:
1980:
1976:
1948:
1944:
1909:
1905:
1876:
1870:
1811:
1782:
1776:
1751:
1745:
1715:
1709:
1667:
1631:
1627:
1581:
1575:
1538:
1537:, Series B,
1534:
1500:
1499:, Series B,
1494:
1463:
1424:math/0212070
1414:
1408:
1347:
1333:
1312:
1300:
1284:
1272:
1260:
1248:
1225:
1213:
1156:
1110:
1083:
1042:
1037:dense graphs
1032:
1021:
1015:
1008:
1000:
990:
977:
972:
968:
963:
959:
955:
951:
947:
943:
939:
935:
931:
927:
917:
901:
898:
874:
845:
827:
805:
799:
794:
790:
786:
782:
774:
770:
764:
760:Minty (1980)
756:Sbihi (1980)
733:
715:
711:
707:
703:
699:
695:
690:
685:
681:
676:
659:
647:
643:
639:
635:
631:
627:
623:
619:
615:
611:
607:
605:
600:
596:
592:
588:
584:
580:
576:
572:
568:
564:
561:
543:
537:
533:
529:
510:cubic graphs
503:
485:
465:
461:
457:
453:
451:
441:
437:
431:
422:
413:
404:
390:
382:
377:
366:
362:
346:
342:
338:
336:
222:
215:
208:
203:then by the
197:
193:
186:
179:
172:
168:
164:
160:
156:
152:
148:
144:
140:
136:
132:
128:
82:
66:neighborhood
56:(that is, a
50:
45:
32:
29:graph theory
26:
2100:: 307–309,
1634:: 449–467,
1344:Sack, J.-R.
946:but not by
464:nodes, for
448:Enumeration
333:Recognition
311:icosahedron
287:tetrahedron
85:line graphs
2221:Categories
1326:References
516:problems.
303:isomorphic
295:octahedron
254:formed as
234:complement
126:line graph
74:complement
58:star graph
2209:MathWorld
1919:1212.3036
1821:1012.0012
1591:1011.6239
1543:CiteSeerX
1441:119151552
1367:1813/6891
1151:, p. 132.
987:Structure
979:graph is
520:Matchings
283:polytopes
279:polyhedra
1855:citation
1768:16308467
1698:13353335
1658:18909734
1616:16339210
1486:(2008),
1455:(2005),
1400:(2006),
1105:, p. 89.
1078:, p. 88.
904:-bounded
846:odd hole
746:finds a
111:Examples
2177:0323648
2169:2039666
2137:0553650
2106:0351881
2085:1972075
2020:0579076
1989:0412042
1965:1761552
1936:7385598
1893:0508603
1848:3080073
1799:2046636
1734:1432221
1650:0177907
1608:2894366
1567:2718677
1519:2418774
1472:2187738
958:, then
496:in the
493:A086991
478:in the
475:A022562
429:√
420:√
411:√
402:√
388:√
357:of its
315:16-cell
305:to the
291:simplex
236:of any
229:graphs.
72:is the
68:of any
2175:
2167:
2135:
2104:
2083:
2018:
1987:
1963:
1934:
1891:
1846:
1836:
1797:
1766:
1732:
1696:
1686:
1656:
1648:
1614:
1606:
1565:
1545:
1517:
1470:
1439:
1374:
618:, and
250:, the
221:, and
185:, and
70:vertex
39:as an
23:A claw
2165:JSTOR
2059:(PDF)
1932:S2CID
1914:arXiv
1844:S2CID
1816:arXiv
1764:S2CID
1694:S2CID
1672:(PDF)
1654:S2CID
1612:S2CID
1586:arXiv
1491:(PDF)
1460:(PDF)
1437:S2CID
1419:arXiv
1405:(PDF)
1059:Notes
854:color
654:of a
76:of a
1861:link
1834:ISBN
1684:ISBN
1372:ISBN
934:and
758:and
634:and
599:and
587:nor
567:and
532:and
498:OEIS
480:OEIS
355:cube
324:, a
320:The
281:and
266:The
232:The
124:The
37:claw
2157:doi
2123:doi
2073:doi
2041:doi
2006:doi
1953:doi
1924:doi
1881:doi
1826:doi
1787:doi
1783:276
1756:doi
1720:doi
1716:164
1676:doi
1636:doi
1596:doi
1582:412
1553:doi
1539:100
1505:doi
1429:doi
1415:164
1362:hdl
1354:doi
1236:in
742:of
734:An
444:).
380:).
192:in
54:1,3
27:In
2223::
2206:,
2202:,
2173:MR
2171:,
2163:,
2153:42
2151:,
2133:MR
2131:,
2119:29
2117:,
2102:MR
2098:15
2096:,
2081:MR
2079:,
2069:16
2067:,
2061:,
2037:44
2035:,
2031:,
2016:MR
2014:,
2002:28
2000:,
1985:MR
1981:17
1979:,
1961:MR
1959:,
1949:74
1947:,
1930:,
1922:,
1910:78
1908:,
1889:MR
1887:,
1875:,
1857:}}
1853:{{
1842:,
1832:,
1824:,
1795:MR
1793:,
1781:,
1762:,
1752:16
1750:,
1730:MR
1728:,
1714:,
1692:,
1682:,
1652:,
1646:MR
1644:,
1632:17
1630:,
1610:,
1604:MR
1602:,
1594:,
1580:,
1563:MR
1561:,
1551:,
1529:;
1515:MR
1513:,
1501:98
1493:,
1482:;
1468:MR
1462:,
1451:;
1435:,
1427:,
1413:,
1407:,
1396:;
1392:;
1388:;
1370:,
1360:,
1291:;
1198:^
1183:^
1168:^
1139:^
1122:^
1095:^
1066:^
1007:A
828:A
816:,
777::
762:.
689:1,
644:vw
500:).
482:).
214:,
178:,
80:.
43:.
2180:.
2159::
2140:.
2125::
2109:.
2088:.
2075::
2050:.
2043::
2023:.
2008::
1992:.
1968:.
1955::
1939:.
1926::
1916::
1896:.
1883::
1877:7
1865:.
1863:)
1828::
1818::
1802:.
1789::
1771:.
1758::
1737:.
1722::
1701:.
1678::
1661:.
1638::
1619:.
1598::
1588::
1570:.
1555::
1522:.
1507::
1475:.
1444:.
1431::
1421::
1381:.
1364::
1356::
1338:.
1319:.
1307:.
1295:.
1267:.
1255:.
1208:.
1163:.
1134:.
1117:.
1090:.
973:D
969:D
964:v
960:v
956:D
952:v
948:w
944:v
940:D
936:w
932:v
928:D
902:χ
863::
795:I
791:I
787:I
783:I
771:I
716:k
712:k
708:k
704:k
700:k
696:r
691:r
686:K
682:r
660:u
648:u
640:u
636:w
632:v
628:u
624:v
620:w
616:u
612:v
608:u
601:w
597:v
593:u
589:w
585:v
581:u
577:v
573:w
569:v
565:u
538:u
534:w
530:v
466:n
462:n
458:n
454:n
442:m
438:m
432:m
423:m
414:m
405:m
400:2
391:m
378:n
367:n
363:n
347:n
343:m
339:n
317:.
301:(
263:.
244:.
226:3
223:e
219:2
216:e
212:1
209:e
201:4
198:e
194:G
190:3
187:e
183:2
180:e
176:1
173:e
169:G
167:(
165:L
161:G
157:G
155:(
153:L
149:G
145:G
143:(
141:L
137:G
133:G
131:(
129:L
51:K
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
