27:
1185:− 1 â thus, the degeneracy is less than twice the arboricity. One may also compute in polynomial time an orientation of a graph that minimizes the outdegree but is not required to be acyclic. The edges of a graph with such an orientation may be partitioned in the same way into
258:, the minimum number of colors needed to color the vertices so that no two adjacent vertices have the same color; the ordering which determines the coloring number provides an order to color the vertices of G with the coloring number, but in general the chromatic number may be smaller.
285:
or fewer neighbors. The definition would be the same if arbitrary subgraphs are allowed in place of induced subgraphs, as a non-induced subgraph can only have vertex degrees that are smaller than or equal to the vertex degrees in the subgraph induced by the same vertex set.
30:
A 2-degenerate graph: each vertex has at most two neighbors to its left, so the rightmost vertex of any subgraph has degree at most two. Its 2-core, the subgraph remaining after repeatedly deleting vertices of degree less than two, is
2228:
289:
The two concepts of coloring number and degeneracy are equivalent: in any finite graph the degeneracy is just one less than the coloring number. For, if a graph has an ordering with coloring number κ then in each subgraph
1219: + 1; this is proved by a simple induction on the number of vertices which is exactly like the proof of the six-color theorem for planar graphs. Since chromatic number is an upper bound on the order of the
1300:
earlier neighbors. Therefore, the degeneracy is at most equal to the treewidth and at most equal to the pathwidth. However, there exist graphs with bounded degeneracy and unbounded treewidth, such as the
709:
170:
has either an isolated vertex (incident to no edges) or a leaf vertex (incident to exactly one edge); therefore, trees and forests are 1-degenerate graphs. Every 1-degenerate graph is a forest.
748:
361:. Such an orientation can be formed by orienting each edge towards the earlier of its two endpoints in a coloring number ordering. In the other direction, if an orientation with outdegree
2600:
Garcia-Algarra, Javier; Pastor, Juan Manuel; Iriondo, Jose Maria; Galeano, Javier (2017), "Ranking of critical species to preserve the functionality of mutualistic networks using the
1478:
2287:
1543:
in which each vertex has fewer than α neighbors that are earlier in the ordering. The inequality between coloring and chromatic numbers holds also in this infinite setting;
1060:
1510:
1443:
1978:
Eppstein, D., Löffler, M., & Strash, D. (2010). Listing All
Maximal Cliques in Sparse Graphs in Near-Optimal Time. In O. Cheong, K.-Y. Chwa, & K. Park (Eds.),
650:
1128:
540:
1393:
1373:
1101:
1016:
965:
508:
488:
465:
177:
has a vertex of degree five or less; therefore, every planar graph is 5-degenerate, and the degeneracy of any planar graph is at most five. Similarly, every
2174:
2122:
Bader, Gary D.; Hogue, Christopher W. V. (2003), "An automated method for finding molecular complexes in large protein interaction networks",
1523:
Although concepts of degeneracy and coloring number are frequently considered in the context of finite graphs, the original motivation for
569:. A survey of the topic, covering the main concepts, important algorithmic techniques as well as some application domains, may be found in
2731:
2104:
Asahiro, Yuichi; Miyano, Eiji; Ono, Hirotaka; Zenmyo, Kouhei (2006), "Graph orientation algorithms to minimize the maximum outdegree",
2068:-core decomposition: a tool for the visualization of large scale networks", in Weiss, Yair; Schölkopf, Bernhard; Platt, John (eds.),
1200:
orientation (by choosing an outdegree-1 orientation for each pseudoforest), so the minimum outdegree of such an orientation is the
2899:
663:
2351:
2033:
Altaf-Ul-Amin, M.; Nishikata, K.; Koma, T.; Miyasato, T.; Shinbo, Y.; Arifuzzaman, M.; Wada, C.; Maeda, M.; Oshima, T. (2003),
2788:
2034:
250:
in which each vertex has fewer than κ neighbors that are earlier in the ordering. It should be distinguished from the
230:
of the graph is regular of maximum degree. For all other graphs, the degeneracy is strictly less than the maximum degree.
2692:
Kirkpatrick, Scott; Wilcke, Winfried W.; Garner, Robert B.; Huels, Harald (2002), "Percolation in dense storage arrays",
405:
227:
207:
previously-added vertices. It follows that any subgraph of a network formed in this way has a vertex of degree at most
136:
2683:
2113:
714:
3101:
3048:
2841:
2383:
211:(the last vertex in the subgraph to have been added to the graph) and BarabásiâAlbert networks are automatically
3039:
2876:
2095:
226:. More strongly, the degeneracy of a graph equals its maximum vertex degree if and only if at least one of the
2220:
2169:
2767:
Kowalik, Åukasz (2006), "Approximation scheme for lowest outdegree orientation and graph density measures",
3125:
3043:
3011:
1582:
1293:
2898:
Malliaros, Fragkiskos D.; Giatsidis, Christos; Papadopoulos, Apostolos N.; Vazirgiannis, Michalis (2019),
1309:
189:
580:
2552:; Westermann, H. H. (1992), "Forests, frames, and games: algorithms for matroid sums and applications",
1348:-degenerate graphs grows linearly in the number of vertices of the graphs. The conjecture was proven by
2936:(1968), "A min-max theorem for graphs with application to graph coloring", SIAM 1968 National Meeting,
2487:
2320:
Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. ErdÅs on his 60th birthday), Vol. 1
1257:
vertex-disjoint paths. Since these paths must leave the two vertices of the pair via disjoint edges, a
1531:, one may define the coloring number analogously to the definition for finite graphs, as the smallest
3200:
3195:
3072:
2739:
1448:
1269:-cores but based on vertex connectivity have been studied in social network theory under the name of
1032:
2592:
1587:
1243:
1205:
2582:
Gaertler, Marco; Patrignani, Maurizio (2004), "Dynamic analysis of the autonomous system graph",
2417:
1513:
1249:
is a graph that cannot be partitioned into more than one component by the removal of fewer than
2587:
2064:
Alvarez-Hamelin, José Ignacio; Dall'Asta, Luca; Barrat, Alain; Vespignani, Alessandro (2006), "
1483:
350:
2678:, Wiley Series in Discrete Mathematics and Optimization, vol. 39, John Wiley & Sons,
1398:
2961:; Beck, L. L. (1983), "Smallest-last ordering and clustering and graph coloring algorithms",
2756:
2326:, Colloq. Math. Soc. János Bolyai, vol. 10, Amsterdam: North-Holland, pp. 214â240,
1706:
1555:
617:
588:
576:
354:
51:
2864:
1110:
3149:
2986:
2723:
2703:
2510:
2436:
2404:
2331:
2255:
2205:
2083:
2014:
513:
370:
2769:
Proceedings of the 17th
International Symposium on Algorithms and Computation (ISAAC 2006)
2343:
2303:
Graph Theory and
Combinatorics, Proc. Cambridge Combinatorial Conf. in honor of Paul ErdÅs
1208:
is also within a constant factor of the arboricity, and therefore also of the degeneracy.
8:
2108:, Darlinghurst, Australia, Australia: Australian Computer Society, Inc., pp. 11â20,
1270:
1154:
196:
167:
20:
2707:
2440:
2259:
2087:
2070:
Advances in Neural
Information Processing Systems 18: Proceedings of the 2005 Conference
2018:
3174:
3028:
2990:
2963:
2922:
2824:
2806:
2663:
2628:
2571:
2538:
2519:
2460:
2426:
2298:
2279:
2245:
2209:
2183:
2165:
2124:
2073:
1577:
1378:
1358:
1065:
974:
941:
493:
473:
450:
182:
3115:
2715:
2584:
Proc. 2nd
International Workshop on Inter-Domain Performance and Simulation (IPS 2004)
2148:
3166:
3085:
3062:
2890:
2784:
2694:
2679:
2633:
2452:
2396:
2365:
2271:
2236:
2153:
2109:
2091:
2026:
2005:
1253:
vertices, or equivalently a graph in which each pair of vertices can be connected by
178:
3178:
2926:
2575:
2197:
3158:
3134:
3110:
3081:
3057:
3020:
3002:
2994:
2972:
2947:
2914:
2885:
2850:
2828:
2816:
2776:
2748:
2711:
2655:
2623:
2613:
2563:
2542:
2528:
2496:
2444:
2392:
2360:
2263:
2213:
2193:
2143:
2133:
2022:
1201:
1027:
600:
274:
251:
47:
3007:"Structural cohesion and embeddedness: a hierarchical conception of social groups"
2667:
2475:
2448:
2283:
2053:
1547:
state that, at the time of publication of their paper, it was already well known.
3092:
2982:
2719:
2549:
2506:
2400:
2374:
2327:
2267:
2201:
1572:
1551:
1532:
1224:
592:
584:
393:
109:
2820:
2464:
298:
and is last in the ordering has at most κ − 1 neighbors in
3006:
2918:
2517:
Freuder, Eugene C. (1982), "A sufficient condition for backtrack-free search",
2378:
2339:
1983:
1333:
1220:
558:
550:
3139:
2752:
2344:"Planar orientations with low out-degree and compaction of adjacency matrices"
2224:
2106:
CATS '06: Proceedings of the 12th
Computing: The Australasian Theory Symposium
1832:
78:
it is, and is within a constant factor of other sparsity measures such as the
3189:
1844:
1536:
1317:
1289:
562:
246:
to be the least κ for which there exists an ordering of the vertices of
2471:
2314:
2063:
1826:
757:
and repeatedly removing the vertex with the smallest degree. The degeneracy
26:
3170:
3162:
3096:
2958:
2933:
2855:
2646:
2637:
2554:
2479:
2456:
2318:
2275:
2172:(2012), "The sharp threshold for bootstrap percolation in all dimensions",
2157:
1567:
1189:
754:
554:
193:
174:
113:
36:
2897:
2533:
2138:
1982:(Vol. 6506, pp. 403â414). Berlin, Heidelberg: Springer Berlin Heidelberg.
1181: − 1) edges and therefore has a vertex of degree at most 2
570:
2938:
2900:"The core decomposition of networks: theory, algorithms and applications"
2431:
2310:
2250:
1228:
761:
is given by the highest degree of any vertex at the time of its removal.
132:
75:
2977:
2780:
2039:-cores of protein-protein interaction networks and amino acid sequences"
1856:
3032:
2659:
2618:
2567:
2501:
2000:
1302:
1223:, the latter invariant is also at most degeneracy plus one. By using a
1158:
79:
1157:
by choosing one forest for each outgoing edge of each node. Thus, the
2317:(1975), "On the magnitude of generalized Ramsey numbers for graphs",
1908:
1281:
1277:
135:
by an algorithm that repeatedly removes minimum-degree vertices. The
3147:
Wuchty, S.; Almaas, E. (2005), "Peeling the yeast protein network",
3070:
Seidman, Stephen B. (1983), "Network structure and minimum degree",
3024:
2951:
2811:
2078:
1725:)-regular component." In the notation used by Jensen and Toft, col(
750:
2599:
2188:
2032:
1838:
1806:
614:
outline an algorithm to derive the degeneracy ordering of a graph
591:. It consists of selecting a random subset of active cells from a
2163:
1850:
1512:, so the class of graphs with bounded degeneracy is said to have
566:
798:. Initially, these numbers are just the degrees of the vertices.
150:
of the graph and the degeneracy of a graph is the largest value
1227:
algorithm on an ordering with optimal coloring number, one can
1165:
is at most equal to its degeneracy. In the other direction, an
412:
formed by repeatedly deleting all vertices of degree less than
2797:
Lee, Choongbum (2017), "Ramsey numbers of degenerate graphs",
2411:
Dorogovtsev, S. N.; Goltsev, A. V.; Mendes, J. F. F. (2006), "
1340:. Specifically, the conjecture is that for any fixed value of
314: + 1 can be obtained by repeatedly finding a vertex
3099:(1968), "An inequality for the chromatic number of a graph",
2691:
1862:
326:
from the graph, ordering the remaining vertices, and adding
1624:
704:{\displaystyle {\mathcal {O}}(\vert V\vert +\vert E\vert )}
74:-degenerate. The degeneracy of a graph is a measure of how
2644:
Irani, Sandy (1994), "Coloring inductive graphs on-line",
549:-core was introduced to study the clustering structure of
3123:
Venkateswaran, V. (2004), "Minimizing maximum indegree",
2372:
1914:
1527:
was the theory of infinite graphs. For an infinite graph
2410:
1790:
1192:, and conversely any partition of a graph's edges into
2381:(1991), "On the thickness and arboricity of a graph",
2103:
1898:
1636:
1401:
1261:-vertex-connected graph must have degeneracy at least
1204:, which again is at most equal to the degeneracy. The
2695:
Physica A: Statistical
Mechanics and its Applications
2006:
Physica A: Statistical
Mechanics and its Applications
1660:
1600:
1486:
1451:
1381:
1361:
1137:
1113:
1068:
1035:
977:
944:
717:
666:
620:
516:
496:
476:
453:
203:
such that each vertex that is added to the graph has
139:
that are left after all vertices of degree less than
925:to the cell of D corresponding to the new value of
764:In more detail, the algorithm proceeds as follows:
310:-degenerate, then an ordering with coloring number
2581:
1822:
1612:
1504:
1472:
1437:
1387:
1367:
1122:
1095:
1054:
1010:
959:
753:of space, by storing vertices in a degree-indexed
742:
703:
644:
534:
502:
482:
459:
2175:Transactions of the American Mathematical Society
1868:
3187:
3046:(1984), "Graph minors. III. Planar tree-width",
3038:
2729:
1954:
1648:
1630:
2548:
2480:"On chromatic number of graphs and set-systems"
2337:
1890:
1886:
1758:
1215:-degenerate graph has chromatic number at most
233:
131:. The degeneracy of a graph may be computed in
58:: that is, some vertex in the subgraph touches
2219:
1690:
143:have been (repeatedly) removed are called the
3122:
1894:
1550:The degeneracy of random subsets of infinite
743:{\displaystyle {\mathcal {O}}(\vert V\vert )}
3146:
3091:
1984:https://doi.org/10.1007/978-3-642-17517-6_36
1930:
1810:
734:
728:
695:
689:
683:
677:
345: + 1) if and only if the edges of
341:-degenerate (or has coloring number at most
117:
2470:
2072:, vol. 18, The MIT Press, p. 41,
1926:
1642:
1544:
1524:
1169:-vertex graph that can be partitioned into
400:in which all vertices have degree at least
365:is given, an ordering with coloring number
243:
222:-regular graph has degeneracy exactly
3000:
2957:
2673:
2301:(1984), "The evolution of sparse graphs",
2121:
2035:"Prediction of protein functions based on
1942:
1802:
1702:
1666:
1606:
611:
3138:
3114:
3061:
2976:
2889:
2854:
2834:
2810:
2730:Kirousis, L. M.; Thilikos, D. M. (1996),
2627:
2617:
2591:
2532:
2500:
2430:
2415:-core organization of complex networks",
2364:
2309:
2249:
2229:"Emergence of scaling in random networks"
2187:
2147:
2137:
2077:
1966:
1915:Dean, Hutchinson & Scheinerman (1991)
1746:
1729:) is the degeneracy plus one, and Δ(
1678:
1466:
1465:
1150:, then its edges may be partitioned into
595:or other space, and then considering the
373:of the resulting directed acyclic graph.
266:
124:-degenerate graphs have also been called
2835:Lick, Don R.; White, Arthur T. (1970), "
2297:
1791:Dorogovtsev, Goltsev & Mendes (2006)
1782:
938:At the end of the algorithm, any vertex
333:A third, equivalent formulation is that
50:in which every subgraph has a vertex of
25:
3069:
2766:
2674:Jensen, Tommy R.; Toft, Bjarne (2011),
2516:
1902:
1770:
1618:
1146:is oriented acyclically with outdegree
3188:
2932:
2862:
1786:
1742:
1328:such that any two-edge-coloring of an
62:or fewer of the subgraph's edges. The
2771:, Lecture Notes in Computer Science,
2643:
1999:
1874:
1654:
1336:must contain a monochromatic copy of
100:, and is essentially the same as the
1196:pseudoforests leads to an outdegree-
369: + 1 can be obtained as a
181:has degeneracy at most two, and the
66:of a graph is the smallest value of
2796:
1554:has been studied under the name of
1349:
13:
1518:
1312:relates the degeneracy of a graph
1138:Relation to other graph parameters
720:
669:
579:is a random process studied as an
23:of a graph is a different concept.
14:
3212:
2003:(1991), "Bootstrap percolation",
1296:in which each vertex has at most
1062:that are induced by the vertices
553:and to describe the evolution of
404:. Equivalently, it is one of the
85:Degeneracy is also known as the
2305:, Academic Press, pp. 35â57
1823:Gaertler & Patrignani (2004)
1535:α such that there exists a
1235:-degenerate graph using at most
1107:is the first vertex with degree
809:contains a list of the vertices
565:, and resilience of networks in
3102:Journal of Combinatorial Theory
3049:Journal of Combinatorial Theory
2842:Canadian Journal of Mathematics
2384:Journal of Combinatorial Theory
2198:10.1090/S0002-9947-2011-05552-2
1972:
1960:
1948:
1936:
1920:
1880:
1816:
1796:
1776:
1764:
1752:
1736:
1733:) is the maximum vertex degree.
1717:) + 1 if and only if
1473:{\displaystyle d\equiv 0\mod 3}
1461:
238:The coloring number of a graph
2865:"Size and connectivity of the
1955:Robertson & Seymour (1984)
1709:: "It is easy to see that col(
1696:
1684:
1672:
1631:Kirousis & Thilikos (1996)
1414:
1402:
1375:-vertex graph with degeneracy
1090:
1072:
1055:{\displaystyle H_{l}\subset G}
1005:
981:
954:
948:
737:
725:
698:
674:
639:
627:
557:. It has also been applied in
529:
517:
1:
3116:10.1016/S0021-9800(68)80081-X
2716:10.1016/S0378-4371(02)01153-6
2449:10.1103/PhysRevLett.96.040601
1992:
1891:Gabow & Westermann (1992)
1887:Chrobak & Eppstein (1991)
1827:Alvarez-Hamelin et al. (2006)
1759:Chrobak & Eppstein (1991)
1288:, then it is a subgraph of a
790:, the number of neighbors of
606:
420:-core exists, then, clearly,
302:. In the other direction, if
199:is parameterized by a number
19:"K-core" redirects here. The
16:Measurement of graph sparsity
3126:Discrete Applied Mathematics
3086:10.1016/0378-8733(83)90028-X
3063:10.1016/0095-8956(84)90013-3
3012:American Sociological Review
2891:10.1016/0012-365X(91)90162-U
2775:, Springer-Verlag: 557â566,
2397:10.1016/0095-8956(91)90100-X
2366:10.1016/0304-3975(91)90020-3
2352:Theoretical Computer Science
2268:10.1126/science.286.5439.509
2027:10.1016/0378-4371(91)90295-n
1839:Garcia-Algarra et al. (2017)
1691:Barabási & Albert (1999)
1294:perfect elimination ordering
234:Definitions and equivalences
7:
2821:10.4007/annals.2017.185.3.2
1807:Altaf-Ul-Amin et al. (2003)
1749:, Proposition 1, page 1084.
1561:
1130:at the time it is added to
294:the vertex that belongs to
161:
10:
3217:
2919:10.1007/s00778-019-00587-4
2488:Acta Mathematica Hungarica
1980:Algorithms and Computation
1931:Szekeres & Wilf (1968)
1811:Wuchty & Almaas (2005)
768:Initialize an output list
376:
349:can be oriented to form a
261:The degeneracy of a graph
18:
3140:10.1016/j.dam.2003.07.007
2753:10.1137/S0097539793255709
2740:SIAM Journal on Computing
2052:: 498â499, archived from
1927:ErdÅs & Hajnal (1966)
1863:Kirkpatrick et al. (2002)
1643:ErdÅs & Hajnal (1966)
1545:ErdÅs & Hajnal (1966)
1525:ErdÅs & Hajnal (1966)
1505:{\displaystyle n\geq d+3}
1445:maximal cliques whenever
1438:{\textstyle (n-d)3^{d/3}}
330:to the end of the order.
244:ErdÅs & Hajnal (1966)
2869:-core of a random graph"
2732:"The linkage of a graph"
1943:Moody & White (2003)
1803:Bader & Hogue (2003)
1703:Jensen & Toft (2011)
1667:Matula & Beck (1983)
1607:Bader & Hogue (2003)
1593:
1583:Coreâperiphery structure
813:that are not already in
794:that are not already in
612:Matula & Beck (1983)
428:, and the degeneracy of
424:has degeneracy at least
2863:Åuczak, Tomasz (1991),
2676:Graph Coloring Problems
2418:Physical Review Letters
2221:Barabási, Albert-László
2168:; Duminil-Copin, Hugo;
1967:Burr & ErdÅs (1975)
1747:Lick & White (1970)
1679:Lick & White (1970)
1344:, the Ramsey number of
1247:-vertex-connected graph
1239: + 1 colors.
853:, ... until finding an
645:{\displaystyle G=(V,E)}
571:Malliaros et al. (2019)
281:contains a vertex with
267:Lick & White (1970)
185:have degeneracy three.
3163:10.1002/pmic.200400962
2856:10.4153/CJM-1970-125-1
2604:-core decomposition",
2379:Scheinerman, Edward R.
1506:
1474:
1439:
1389:
1369:
1265:. Concepts related to
1124:
1123:{\displaystyle \geq l}
1097:
1056:
1012:
971:edges to the vertices
961:
744:
705:
646:
536:
504:
484:
461:
396:connected subgraph of
351:directed acyclic graph
32:
2839:-degenerate graphs",
2799:Annals of Mathematics
2534:10.1145/322290.322292
2139:10.1186/1471-2105-4-2
1899:Asahiro et al. (2006)
1713:) = Δ(
1588:Cereceda's conjecture
1556:bootstrap percolation
1507:
1475:
1440:
1390:
1370:
1310:BurrâErdÅs conjecture
1125:
1098:
1057:
1013:
962:
845:Scan the array cells
745:
706:
647:
589:distributed computing
577:Bootstrap percolation
563:network visualization
537:
535:{\displaystyle (c+1)}
510:-core but not to any
505:
485:
462:
190:BarabásiâAlbert model
29:
2877:Discrete Mathematics
1895:Venkateswaran (2004)
1851:Balogh et al. (2012)
1484:
1449:
1399:
1379:
1359:
1173:forests has at most
1111:
1066:
1033:
975:
942:
914:, subtract one from
891:to the beginning of
801:Initialize an array
715:
664:
618:
514:
494:
474:
451:
406:connected components
371:topological ordering
322:neighbors, removing
228:connected components
137:connected components
106:SzekeresâWilf number
2978:10.1145/2402.322385
2781:10.1007/11940128_56
2708:2002PhyA..314..220K
2441:2006PhRvL..96d0601D
2375:Hutchinson, Joan P.
2260:1999Sci...286..509B
2088:2005cs........4107A
2019:1991PhyA..171..453A
1539:of the vertices of
1271:structural cohesion
895:and remove it from
583:and as a model for
490:if it belongs to a
408:of the subgraph of
197:scale-free networks
183:Apollonian networks
154:such that it has a
2964:Journal of the ACM
2660:10.1007/BF01294263
2619:10.7717/peerj.3321
2586:, pp. 13â24,
2568:10.1007/BF01758774
2520:Journal of the ACM
2502:10.1007/BF02020444
2125:BMC Bioinformatics
2046:Genome Informatics
1578:Percolation Theory
1502:
1470:
1435:
1385:
1365:
1120:
1093:
1052:
1008:
967:will have at most
957:
902:For each neighbor
740:
701:
642:
532:
500:
480:
457:
33:
3003:White, Douglas R.
2790:978-3-540-49694-6
2244:(5439): 509â512,
1388:{\displaystyle d}
1368:{\displaystyle n}
1096:{\displaystyle L}
1011:{\displaystyle L}
960:{\displaystyle L}
775:Compute a number
545:The concept of a
503:{\displaystyle c}
483:{\displaystyle c}
460:{\displaystyle u}
416:. If a non-empty
388:-core of a graph
179:outerplanar graph
129:-inductive graphs
44:-degenerate graph
3208:
3201:Graph algorithms
3196:Graph invariants
3181:
3143:
3142:
3133:(1â3): 374â378,
3119:
3118:
3097:Wilf, Herbert S.
3093:Szekeres, George
3088:
3066:
3065:
3035:
2997:
2980:
2959:Matula, David W.
2954:
2934:Matula, David W.
2929:
2907:The VLDB Journal
2904:
2894:
2893:
2873:
2868:
2859:
2858:
2849:(5): 1082â1096,
2838:
2831:
2814:
2793:
2763:
2761:
2755:, archived from
2736:
2726:
2702:(1â4): 220â229,
2688:
2670:
2640:
2631:
2621:
2603:
2596:
2595:
2578:
2545:
2536:
2513:
2504:
2484:
2467:
2434:
2432:cond-mat/0509102
2414:
2407:
2373:Dean, Alice M.;
2369:
2368:
2348:
2338:Chrobak, Marek;
2334:
2325:
2306:
2294:
2292:
2286:, archived from
2253:
2251:cond-mat/9910332
2233:
2216:
2191:
2182:(5): 2667â2701,
2164:Balogh, József;
2160:
2151:
2141:
2118:
2100:
2081:
2067:
2060:
2058:
2043:
2038:
2029:
1986:
1976:
1970:
1964:
1958:
1952:
1946:
1940:
1934:
1924:
1918:
1912:
1906:
1884:
1878:
1872:
1866:
1860:
1854:
1848:
1842:
1836:
1830:
1820:
1814:
1800:
1794:
1780:
1774:
1768:
1762:
1756:
1750:
1740:
1734:
1700:
1694:
1688:
1682:
1676:
1670:
1664:
1658:
1652:
1646:
1640:
1634:
1628:
1622:
1616:
1610:
1604:
1511:
1509:
1508:
1503:
1479:
1477:
1476:
1471:
1444:
1442:
1441:
1436:
1434:
1433:
1429:
1394:
1392:
1391:
1386:
1374:
1372:
1371:
1366:
1202:pseudoarboricity
1133:
1129:
1127:
1126:
1121:
1106:
1102:
1100:
1099:
1094:
1061:
1059:
1058:
1053:
1045:
1044:
1025:
1021:
1017:
1015:
1014:
1009:
970:
966:
964:
963:
958:
879:Select a vertex
782:for each vertex
760:
749:
747:
746:
741:
724:
723:
710:
708:
707:
702:
673:
672:
659:
655:
652:with vertex set
651:
649:
648:
643:
603:of this subset.
601:induced subgraph
598:
541:
539:
538:
533:
509:
507:
506:
501:
489:
487:
486:
481:
466:
464:
463:
458:
275:induced subgraph
273:such that every
252:chromatic number
70:for which it is
48:undirected graph
3216:
3215:
3211:
3210:
3209:
3207:
3206:
3205:
3186:
3185:
3184:
3073:Social Networks
3040:Robertson, Neil
3025:10.2307/3088904
2952:10.1137/1010115
2902:
2871:
2866:
2836:
2791:
2759:
2734:
2686:
2601:
2482:
2412:
2346:
2340:Eppstein, David
2323:
2311:Burr, Stefan A.
2290:
2231:
2116:
2098:
2065:
2056:
2041:
2036:
1995:
1990:
1989:
1977:
1973:
1965:
1961:
1953:
1949:
1941:
1937:
1925:
1921:
1913:
1909:
1885:
1881:
1873:
1869:
1861:
1857:
1849:
1845:
1837:
1833:
1821:
1817:
1801:
1797:
1783:Bollobás (1984)
1781:
1777:
1769:
1765:
1757:
1753:
1741:
1737:
1701:
1697:
1689:
1685:
1677:
1673:
1665:
1661:
1653:
1649:
1641:
1637:
1629:
1625:
1617:
1613:
1605:
1601:
1596:
1573:Network science
1564:
1533:cardinal number
1521:
1519:Infinite graphs
1485:
1482:
1481:
1450:
1447:
1446:
1425:
1421:
1417:
1400:
1397:
1396:
1380:
1377:
1376:
1360:
1357:
1356:
1276:If a graph has
1225:greedy coloring
1140:
1131:
1112:
1109:
1108:
1104:
1067:
1064:
1063:
1040:
1036:
1034:
1031:
1030:
1023:
1019:
976:
973:
972:
968:
943:
940:
939:
930:
919:
910:not already in
822:
780:
758:
719:
718:
716:
713:
712:
668:
667:
665:
662:
661:
657:
653:
619:
616:
615:
609:
596:
585:fault tolerance
551:social networks
515:
512:
511:
495:
492:
491:
475:
472:
471:
452:
449:
448:
432:is the largest
382:
265:was defined by
242:was defined by
236:
192:for generating
164:
102:coloring number
24:
17:
12:
11:
5:
3214:
3204:
3203:
3198:
3183:
3182:
3157:(2): 444â449,
3144:
3120:
3089:
3080:(3): 269â287,
3067:
3036:
3001:Moody, James;
2998:
2971:(3): 417â427,
2955:
2946:(4): 481â482,
2930:
2895:
2860:
2832:
2805:(3): 791â829,
2794:
2789:
2764:
2747:(3): 626â647,
2727:
2689:
2684:
2671:
2641:
2597:
2593:10.1.1.81.6841
2579:
2562:(1): 465â497,
2546:
2514:
2495:(1â2): 61â99,
2476:Hajnal, András
2468:
2408:
2391:(1): 147â151,
2370:
2359:(2): 243â266,
2335:
2307:
2299:Bollobás, Béla
2295:
2217:
2170:Morris, Robert
2166:Bollobás, Béla
2161:
2119:
2114:
2101:
2096:
2061:
2030:
2013:(3): 453â470,
1996:
1994:
1991:
1988:
1987:
1971:
1959:
1947:
1935:
1919:
1907:
1903:Kowalik (2006)
1879:
1867:
1855:
1843:
1831:
1815:
1795:
1775:
1771:Seidman (1983)
1763:
1751:
1735:
1695:
1683:
1671:
1659:
1647:
1635:
1623:
1619:Freuder (1982)
1611:
1598:
1597:
1595:
1592:
1591:
1590:
1585:
1580:
1575:
1570:
1563:
1560:
1520:
1517:
1501:
1498:
1495:
1492:
1489:
1469:
1464:
1460:
1457:
1454:
1432:
1428:
1424:
1420:
1416:
1413:
1410:
1407:
1404:
1384:
1364:
1334:complete graph
1221:maximum clique
1139:
1136:
1119:
1116:
1092:
1089:
1086:
1083:
1080:
1077:
1074:
1071:
1051:
1048:
1043:
1039:
1007:
1004:
1001:
998:
995:
992:
989:
986:
983:
980:
956:
953:
950:
947:
936:
935:
934:
933:
928:
917:
900:
877:
862:
836:
829:
820:
799:
778:
773:
739:
736:
733:
730:
727:
722:
700:
697:
694:
691:
688:
685:
682:
679:
676:
671:
641:
638:
635:
632:
629:
626:
623:
608:
605:
581:epidemic model
559:bioinformatics
531:
528:
525:
522:
519:
499:
479:
456:
381:
375:
235:
232:
163:
160:
15:
9:
6:
4:
3:
2:
3213:
3202:
3199:
3197:
3194:
3193:
3191:
3180:
3176:
3172:
3168:
3164:
3160:
3156:
3152:
3151:
3145:
3141:
3136:
3132:
3128:
3127:
3121:
3117:
3112:
3108:
3104:
3103:
3098:
3094:
3090:
3087:
3083:
3079:
3075:
3074:
3068:
3064:
3059:
3055:
3051:
3050:
3045:
3044:Seymour, Paul
3041:
3037:
3034:
3030:
3026:
3022:
3018:
3014:
3013:
3008:
3004:
2999:
2996:
2992:
2988:
2984:
2979:
2974:
2970:
2966:
2965:
2960:
2956:
2953:
2949:
2945:
2941:
2940:
2935:
2931:
2928:
2924:
2920:
2916:
2912:
2908:
2901:
2896:
2892:
2887:
2883:
2879:
2878:
2870:
2861:
2857:
2852:
2848:
2844:
2843:
2833:
2830:
2826:
2822:
2818:
2813:
2808:
2804:
2800:
2795:
2792:
2786:
2782:
2778:
2774:
2770:
2765:
2762:on 2011-07-21
2758:
2754:
2750:
2746:
2742:
2741:
2733:
2728:
2725:
2721:
2717:
2713:
2709:
2705:
2701:
2697:
2696:
2690:
2687:
2685:9781118030745
2681:
2677:
2672:
2669:
2665:
2661:
2657:
2653:
2649:
2648:
2642:
2639:
2635:
2630:
2625:
2620:
2615:
2611:
2607:
2598:
2594:
2589:
2585:
2580:
2577:
2573:
2569:
2565:
2561:
2557:
2556:
2551:
2547:
2544:
2540:
2535:
2530:
2526:
2522:
2521:
2515:
2512:
2508:
2503:
2498:
2494:
2490:
2489:
2481:
2477:
2473:
2469:
2466:
2462:
2458:
2454:
2450:
2446:
2442:
2438:
2433:
2428:
2425:(4): 040601,
2424:
2420:
2419:
2409:
2406:
2402:
2398:
2394:
2390:
2386:
2385:
2380:
2376:
2371:
2367:
2362:
2358:
2354:
2353:
2345:
2341:
2336:
2333:
2329:
2322:
2321:
2316:
2312:
2308:
2304:
2300:
2296:
2293:on 2006-11-11
2289:
2285:
2281:
2277:
2273:
2269:
2265:
2261:
2257:
2252:
2247:
2243:
2239:
2238:
2230:
2226:
2222:
2218:
2215:
2211:
2207:
2203:
2199:
2195:
2190:
2185:
2181:
2177:
2176:
2171:
2167:
2162:
2159:
2155:
2150:
2145:
2140:
2135:
2131:
2127:
2126:
2120:
2117:
2115:1-920682-33-3
2111:
2107:
2102:
2099:
2093:
2089:
2085:
2080:
2075:
2071:
2062:
2059:on 2007-09-27
2055:
2051:
2047:
2040:
2031:
2028:
2024:
2020:
2016:
2012:
2008:
2007:
2002:
1998:
1997:
1985:
1981:
1975:
1968:
1963:
1956:
1951:
1944:
1939:
1932:
1928:
1923:
1916:
1911:
1904:
1900:
1896:
1892:
1888:
1883:
1876:
1871:
1864:
1859:
1852:
1847:
1840:
1835:
1828:
1824:
1819:
1812:
1808:
1804:
1799:
1792:
1788:
1787:Åuczak (1991)
1784:
1779:
1772:
1767:
1760:
1755:
1748:
1744:
1743:Matula (1968)
1739:
1732:
1728:
1724:
1721:has a Δ(
1720:
1716:
1712:
1708:
1704:
1699:
1692:
1687:
1680:
1675:
1668:
1663:
1656:
1651:
1644:
1639:
1632:
1627:
1620:
1615:
1608:
1603:
1599:
1589:
1586:
1584:
1581:
1579:
1576:
1574:
1571:
1569:
1566:
1565:
1559:
1557:
1553:
1548:
1546:
1542:
1538:
1537:well-ordering
1534:
1530:
1526:
1516:
1515:
1499:
1496:
1493:
1490:
1487:
1467:
1462:
1458:
1455:
1452:
1430:
1426:
1422:
1418:
1411:
1408:
1405:
1382:
1362:
1353:
1351:
1347:
1343:
1339:
1335:
1331:
1327:
1323:
1319:
1318:Ramsey number
1315:
1311:
1306:
1304:
1299:
1295:
1291:
1290:chordal graph
1287:
1283:
1279:
1274:
1272:
1268:
1264:
1260:
1256:
1252:
1248:
1246:
1240:
1238:
1234:
1230:
1226:
1222:
1218:
1214:
1209:
1207:
1203:
1199:
1195:
1191:
1190:pseudoforests
1188:
1184:
1180:
1176:
1172:
1168:
1164:
1160:
1156:
1153:
1149:
1145:
1135:
1117:
1114:
1087:
1084:
1081:
1078:
1075:
1069:
1049:
1046:
1041:
1037:
1029:
1002:
999:
996:
993:
990:
987:
984:
978:
951:
945:
931:
924:
920:
913:
909:
905:
901:
898:
894:
890:
886:
882:
878:
875:
871:
867:
863:
860:
856:
852:
848:
844:
843:
841:
837:
834:
830:
827:
824: =
823:
816:
812:
808:
804:
800:
797:
793:
789:
785:
781:
774:
771:
767:
766:
765:
762:
756:
752:
731:
692:
686:
680:
656:and edge set
636:
633:
630:
624:
621:
613:
604:
602:
599:-core of the
594:
590:
586:
582:
578:
574:
572:
568:
564:
560:
556:
555:random graphs
552:
548:
543:
526:
523:
520:
497:
477:
470:
454:
445:
443:
439:
435:
431:
427:
423:
419:
415:
411:
407:
403:
399:
395:
391:
387:
379:
374:
372:
368:
364:
360:
356:
352:
348:
344:
340:
336:
331:
329:
325:
321:
318:with at most
317:
313:
309:
305:
301:
297:
293:
287:
284:
280:
276:
272:
269:as the least
268:
264:
259:
257:
253:
249:
245:
241:
231:
229:
225:
221:
216:
215:-degenerate.
214:
210:
206:
202:
198:
195:
191:
186:
184:
180:
176:
173:Every finite
171:
169:
166:Every finite
159:
157:
153:
149:
147:
142:
138:
134:
130:
128:
123:
119:
115:
112: and
111:
108:(named after
107:
103:
99:
95:
91:
89:
83:
81:
77:
73:
69:
65:
61:
57:
53:
49:
45:
43:
38:
28:
22:
3154:
3148:
3130:
3124:
3106:
3100:
3077:
3071:
3056:(1): 49â64,
3053:
3052:, Series B,
3047:
3016:
3010:
2968:
2962:
2943:
2937:
2910:
2906:
2884:(1): 61â68,
2881:
2875:
2846:
2840:
2802:
2798:
2772:
2768:
2757:the original
2744:
2738:
2699:
2693:
2675:
2654:(1): 53â72,
2651:
2647:Algorithmica
2645:
2609:
2605:
2583:
2559:
2555:Algorithmica
2553:
2550:Gabow, H. N.
2527:(1): 24â32,
2524:
2518:
2492:
2486:
2422:
2416:
2388:
2387:, Series B,
2382:
2356:
2350:
2319:
2302:
2288:the original
2241:
2235:
2225:Albert, Réka
2179:
2173:
2129:
2123:
2105:
2069:
2054:the original
2049:
2045:
2010:
2004:
1979:
1974:
1962:
1950:
1938:
1922:
1910:
1882:
1875:Adler (1991)
1870:
1858:
1846:
1834:
1818:
1798:
1778:
1766:
1754:
1738:
1730:
1726:
1722:
1718:
1714:
1710:
1698:
1686:
1674:
1662:
1655:Irani (1994)
1650:
1638:
1626:
1614:
1602:
1568:Graph theory
1549:
1540:
1528:
1522:
1514:few cliques.
1395:has at most
1354:
1345:
1341:
1337:
1329:
1325:
1324:, the least
1321:
1313:
1307:
1297:
1292:which has a
1285:
1275:
1266:
1262:
1258:
1254:
1250:
1244:
1241:
1236:
1232:
1216:
1212:
1210:
1197:
1193:
1186:
1182:
1178:
1174:
1170:
1166:
1162:
1151:
1147:
1143:
1141:
937:
926:
922:
915:
911:
907:
903:
896:
892:
888:
884:
880:
873:
869:
865:
861:is nonempty.
858:
854:
850:
846:
839:
832:
825:
818:
814:
810:
806:
802:
795:
791:
787:
783:
776:
769:
763:
755:bucket queue
610:
575:
546:
544:
468:
446:
441:
437:
433:
429:
425:
421:
417:
413:
409:
401:
397:
389:
385:
383:
377:
366:
362:
358:
346:
342:
338:
334:
332:
327:
323:
319:
315:
311:
307:
303:
299:
295:
291:
288:
282:
278:
270:
262:
260:
255:
247:
239:
237:
223:
219:
217:
212:
208:
204:
200:
187:
175:planar graph
172:
165:
155:
151:
145:
144:
140:
126:
125:
121:
105:
101:
97:
93:
90:-core number
87:
86:
84:
82:of a graph.
71:
67:
63:
59:
55:
41:
40:
37:graph theory
34:
3019:(1): 1â25,
2939:SIAM Review
2472:ErdÅs, Paul
2315:ErdÅs, Paul
2001:Adler, Joan
1303:grid graphs
1229:graph color
1142:If a graph
831:Initialize
133:linear time
3190:Categories
3150:Proteomics
2812:1505.04773
2097:0262232537
2079:cs/0504107
1993:References
1707:p. 78
1350:Lee (2017)
1159:arboricity
1022:-cores of
857:for which
817:for which
805:such that
607:Algorithms
436:for which
80:arboricity
64:degeneracy
2913:: 61â92,
2612:: e3321,
2588:CiteSeerX
2189:1010.3326
1491:≥
1456:≡
1409:−
1282:pathwidth
1278:treewidth
1206:thickness
1115:≥
1082:…
1047:⊂
1028:subgraphs
1000:−
991:…
921:and move
711:time and
447:A vertex
355:outdegree
3179:17659720
3171:15627958
3005:(2003),
2927:85519668
2638:28533969
2576:40358357
2478:(1966),
2457:16486798
2342:(1991),
2276:10521342
2227:(1999),
2158:12525261
2132:(1): 2,
1562:See also
1552:lattices
1332:-vertex
1284:at most
1103:, where
1026:are the
469:coreness
357:at most
162:Examples
110:Szekeres
54:at most
3109:: 1â3,
3033:3088904
2995:4417741
2987:0709826
2829:7974973
2724:1961703
2704:Bibcode
2629:5438587
2543:8624975
2511:0193025
2437:Bibcode
2405:1109429
2332:0371701
2256:Bibcode
2237:Science
2214:2708046
2206:2888224
2084:Bibcode
2015:Bibcode
1316:to the
1155:forests
868:to max(
842:times:
838:Repeat
593:lattice
567:ecology
542:-core.
444:-core.
394:maximal
158:-core.
116: (
98:linkage
31:shaded.
3177:
3169:
3031:
2993:
2985:
2925:
2827:
2787:
2722:
2682:
2668:181800
2666:
2636:
2626:
2590:
2574:
2541:
2509:
2463:
2455:
2403:
2330:
2284:524106
2282:
2274:
2212:
2204:
2156:
2149:149346
2146:
2112:
2094:
1018:. The
887:. Add
440:has a
380:-Cores
218:Every
194:random
168:forest
148:-cores
96:, and
76:sparse
52:degree
46:is an
3175:S2CID
3029:JSTOR
2991:S2CID
2923:S2CID
2903:(PDF)
2872:(PDF)
2825:S2CID
2807:arXiv
2760:(PDF)
2735:(PDF)
2664:S2CID
2606:PeerJ
2572:S2CID
2539:S2CID
2483:(PDF)
2461:S2CID
2427:arXiv
2347:(PDF)
2324:(PDF)
2291:(PDF)
2280:S2CID
2246:arXiv
2232:(PDF)
2210:S2CID
2184:arXiv
2074:arXiv
2057:(PDF)
2042:(PDF)
1594:Notes
883:from
835:to 0.
751:words
392:is a
353:with
94:width
3167:PMID
2785:ISBN
2773:4288
2680:ISBN
2634:PMID
2465:2035
2453:PMID
2272:PMID
2154:PMID
2110:ISBN
2092:ISBN
1480:and
1355:Any
1308:The
864:Set
587:for
467:has
188:The
120:)).
118:1968
114:Wilf
39:, a
21:core
3159:doi
3135:doi
3131:143
3111:doi
3082:doi
3058:doi
3021:doi
2973:doi
2948:doi
2915:doi
2886:doi
2851:doi
2817:doi
2803:185
2777:doi
2749:doi
2712:doi
2700:314
2656:doi
2624:PMC
2614:doi
2564:doi
2529:doi
2497:doi
2445:doi
2393:doi
2361:doi
2264:doi
2242:286
2194:doi
2180:364
2144:PMC
2134:doi
2023:doi
2011:171
1463:mod
1320:of
1280:or
1161:of
906:of
786:in
660:in
337:is
306:is
277:of
254:of
104:or
35:In
3192::
3173:,
3165:,
3153:,
3129:,
3105:,
3095:;
3076:,
3054:36
3042:;
3027:,
3017:68
3015:,
3009:,
2989:,
2983:MR
2981:,
2969:30
2967:,
2944:10
2942:,
2921:,
2911:29
2909:,
2905:,
2882:91
2880:,
2874:,
2847:22
2845:,
2823:,
2815:,
2801:,
2783:,
2745:25
2743:,
2737:,
2720:MR
2718:,
2710:,
2698:,
2662:,
2652:11
2650:,
2632:,
2622:,
2608:,
2570:,
2558:,
2537:,
2525:29
2523:,
2507:MR
2505:,
2493:17
2491:,
2485:,
2474:;
2459:,
2451:,
2443:,
2435:,
2423:96
2421:,
2401:MR
2399:,
2389:52
2377:;
2357:86
2355:,
2349:,
2328:MR
2313:;
2278:,
2270:,
2262:,
2254:,
2240:,
2234:,
2223:;
2208:,
2202:MR
2200:,
2192:,
2178:,
2152:,
2142:,
2128:,
2090:,
2082:,
2050:14
2048:,
2044:,
2021:,
2009:,
1929:;
1901:;
1897:;
1893:;
1889:;
1825:;
1809:;
1805:;
1785:;
1745:;
1705:,
1558:.
1352:.
1305:.
1273:.
1242:A
1231:a
1211:A
1134:.
849:,
573:.
561:,
384:A
92:,
3161::
3155:5
3137::
3113::
3107:4
3084::
3078:5
3060::
3023::
2975::
2950::
2917::
2888::
2867:k
2853::
2837:k
2819::
2809::
2779::
2751::
2714::
2706::
2658::
2616::
2610:5
2602:k
2566::
2560:7
2531::
2499::
2447::
2439::
2429::
2413:k
2395::
2363::
2266::
2258::
2248::
2196::
2186::
2136::
2130:4
2086::
2076::
2066:k
2037:k
2025::
2017::
1969:.
1957:.
1945:.
1933:.
1917:.
1905:.
1877:.
1865:.
1853:.
1841:.
1829:.
1813:.
1793:.
1789:;
1773:.
1761:.
1731:G
1727:G
1723:G
1719:G
1715:G
1711:G
1693:.
1681:.
1669:.
1657:.
1645:.
1633:.
1621:.
1609:.
1541:G
1529:G
1500:3
1497:+
1494:d
1488:n
1468:3
1459:0
1453:d
1431:3
1427:/
1423:d
1419:3
1415:)
1412:d
1406:n
1403:(
1383:d
1363:n
1346:k
1342:k
1338:G
1330:n
1326:n
1322:G
1314:G
1298:k
1286:k
1267:k
1263:k
1259:k
1255:k
1251:k
1245:k
1237:k
1233:k
1217:k
1213:k
1198:k
1194:k
1187:k
1183:k
1179:n
1177:(
1175:k
1171:k
1167:n
1163:G
1152:k
1148:k
1144:G
1132:L
1118:l
1105:i
1091:]
1088:i
1085:,
1079:,
1076:1
1073:[
1070:L
1050:G
1042:l
1038:H
1024:G
1020:l
1006:]
1003:1
997:i
994:,
988:,
985:1
982:[
979:L
969:k
955:]
952:i
949:[
946:L
932:.
929:w
927:d
923:w
918:w
916:d
912:L
908:v
904:w
899:.
897:D
893:L
889:v
885:D
881:v
876:)
874:i
872:,
870:k
866:k
859:D
855:i
851:D
847:D
840:n
833:k
828:.
826:i
821:v
819:d
815:L
811:v
807:D
803:D
796:L
792:v
788:G
784:v
779:v
777:d
772:.
770:L
759:k
738:)
735:|
732:V
729:|
726:(
721:O
699:)
696:|
693:E
690:|
687:+
684:|
681:V
678:|
675:(
670:O
658:E
654:V
640:)
637:E
634:,
631:V
628:(
625:=
622:G
597:k
547:k
530:)
527:1
524:+
521:c
518:(
498:c
478:c
455:u
442:k
438:G
434:k
430:G
426:k
422:G
418:k
414:k
410:G
402:k
398:G
390:G
386:k
378:k
367:k
363:k
359:k
347:G
343:k
339:k
335:G
328:v
324:v
320:k
316:v
312:k
308:k
304:G
300:H
296:H
292:H
283:k
279:G
271:k
263:G
256:G
248:G
240:G
224:k
220:k
213:m
209:m
205:m
201:m
156:k
152:k
146:k
141:k
127:k
122:k
88:k
72:k
68:k
60:k
56:k
42:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
