Degeneracy (graph theory)

Last updated October 21, 2024

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

Degeneracy is also known as the k-core number,^[1]width,^[2] and linkage,^[3] and is essentially the same as the coloring number^[4] or Szekeres–Wilf number (named after Szekeres and Wilf ( 1968 )). k-degenerate graphs have also been called k-inductive graphs.^[5] The degeneracy of a graph may be computed in linear time by an algorithm that repeatedly removes minimum-degree vertices.^[6] The connected components that are left after all vertices of degree less than k have been (repeatedly) removed are called the k-cores of the graph and the degeneracy of a graph is the largest value k such that it has a k-core.

Examples

Every finite forest 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.

Every finite planar graph 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 outerplanar graph has degeneracy at most two,^[7] and the Apollonian networks have degeneracy three.

The Barabási–Albert model for generating random scale-free networks ^[8] is parameterized by a number m such that each vertex that is added to the graph has m previously-added vertices. It follows that any subgraph of a network formed in this way has a vertex of degree at most m (the last vertex in the subgraph to have been added to the graph) and Barabási–Albert networks are automatically m-degenerate.

Every k-regular graph has degeneracy exactly k. More strongly, the degeneracy of a graph equals its maximum vertex degree if and only if at least one of the connected components of the graph is regular of maximum degree. For all other graphs, the degeneracy is strictly less than the maximum degree.^[9]

Definitions and equivalences

The coloring number of a graph G was defined by Erdős & Hajnal (1966) to be the least κ for which there exists an ordering of the vertices of G in which each vertex has fewer than κ neighbors that are earlier in the ordering. It should be distinguished from the chromatic number of G, 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.

The degeneracy of a graph G was defined by Lick & White (1970) as the least k such that every induced subgraph of G contains a vertex with k 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.

The two concepts of coloring number and degeneracy are equivalent: in any finite graph the degeneracy is just one less than the coloring number.^[10] For, if a graph has an ordering with coloring number κ then in each subgraph H the vertex that belongs to H and is last in the ordering has at most κ − 1 neighbors in H. In the other direction, if G is k-degenerate, then an ordering with coloring number k + 1 can be obtained by repeatedly finding a vertex v with at most k neighbors, removing v from the graph, ordering the remaining vertices, and adding v to the end of the order.

A third, equivalent formulation is that G is k-degenerate (or has coloring number at most k + 1) if and only if the edges of G can be oriented to form a directed acyclic graph with outdegree at most k.^[11] 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 k is given, an ordering with coloring number k + 1 can be obtained as a topological ordering of the resulting directed acyclic graph.

k-Cores

A k-core of a graph G is a maximal connected subgraph of G in which all vertices have degree at least k. Equivalently, it is one of the connected components of the subgraph of G formed by repeatedly deleting all vertices of degree less than k. If a non-empty k-core exists, then, clearly, G has degeneracy at least k, and the degeneracy of G is the largest k for which G has a k-core.

A vertex $u$ has coreness $c$ if it belongs to a $c$ -core but not to any $(c+1)$ -core.

The concept of a k-core was introduced to study the clustering structure of social networks ^[12] and to describe the evolution of random graphs.^[13] It has also been applied in bioinformatics,^[14] network visualization,^[15] and resilience of networks in ecology.^[16] A survey of the topic, covering the main concepts, important algorithmic techniques as well as some application domains, may be found in Malliaros et al. (2019).

Bootstrap percolation is a random process studied as an epidemic model ^[17] and as a model for fault tolerance for distributed computing.^[18] It consists of selecting a random subset of active cells from a lattice or other space, and then considering the $k$ -core of the induced subgraph of this subset.^[19]

Algorithms

Matula & Beck (1983) outline an algorithm to derive the degeneracy ordering of a graph $G=(V,E)$ with vertex set $V$ and edge set $E$ in ${\mathcal {O}}(\vert V\vert +\vert E\vert )$ time and ${\mathcal {O}}(\vert V\vert )$ words of space, by storing vertices in a degree-indexed bucket queue and repeatedly removing the vertex with the smallest degree. The degeneracy $k$ is given by the highest degree of any vertex at the time of its removal.

In more detail, the algorithm proceeds as follows:

Initialize an output list L.
Compute a number d_v for each vertex v in G, the number of neighbors of v that are not already in L. Initially, these numbers are just the degrees of the vertices.
Initialize an array D such that D[i] contains a list of the vertices v that are not already in L for which d_v = i.
Initialize k to 0.
Repeat n times:
- Scan the array cells D[0], D[1], ... until finding an i for which D[i] is nonempty.
- Set k to max(k,i)
- Select a vertex v from D[i]. Add v to the beginning of L and remove it from D[i].
- For each neighbor w of v not already in L, subtract one from d_w and move w to the cell of D corresponding to the new value of d_w.

At the end of the algorithm, any vertex $L[i]$ will have at most $k$ edges to the vertices $L[1,\ldots ,i-1]$ . The $l$ -cores of $G$ are the subgraphs $H_{l}\subset G$ that are induced by the vertices $L[1,\ldots ,i]$ , where $i$ is the first vertex with degree $\geq l$ at the time it is added to $L$ .

Relation to other graph parameters

If a graph G is oriented acyclically with outdegree k, then its edges may be partitioned into k forests by choosing one forest for each outgoing edge of each node. Thus, the arboricity of G is at most equal to its degeneracy. In the other direction, an n-vertex graph that can be partitioned into k forests has at most k(n − 1) edges and therefore has a vertex of degree at most 2k− 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 k pseudoforests, and conversely any partition of a graph's edges into k pseudoforests leads to an outdegree-k orientation (by choosing an outdegree-1 orientation for each pseudoforest), so the minimum outdegree of such an orientation is the pseudoarboricity, which again is at most equal to the degeneracy.^[20] The thickness is also within a constant factor of the arboricity, and therefore also of the degeneracy.^[21]

A k-degenerate graph has chromatic number at most k + 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 maximum clique, the latter invariant is also at most degeneracy plus one. By using a greedy coloring algorithm on an ordering with optimal coloring number, one can graph color a k-degenerate graph using at most k + 1 colors.^[22]

A k-vertex-connected graph is a graph that cannot be partitioned into more than one component by the removal of fewer than k vertices, or equivalently a graph in which each pair of vertices can be connected by k vertex-disjoint paths. Since these paths must leave the two vertices of the pair via disjoint edges, a k-vertex-connected graph must have degeneracy at least k. Concepts related to k-cores but based on vertex connectivity have been studied in social network theory under the name of structural cohesion.^[23]

If a graph has treewidth or pathwidth at most k, then it is a subgraph of a chordal graph which has a perfect elimination ordering in which each vertex has at most k 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 grid graphs.^[24]

The Burr–Erdős conjecture relates the degeneracy of a graph G to the Ramsey number of G, the least n such that any two-edge-coloring of an n-vertex complete graph must contain a monochromatic copy of G. Specifically, the conjecture is that for any fixed value of k, the Ramsey number of k-degenerate graphs grows linearly in the number of vertices of the graphs.^[25] The conjecture was proven by Lee (2017).

Any $n$ -vertex graph with degeneracy $d$ has at most ${\textstyle (n-d)3^{d/3}}$ maximal cliques whenever $d\equiv 0\mod 3$ and $n\geq d+3$ ,^[26] so the class of graphs with bounded degeneracy is said to have few cliques.

Infinite graphs

Although concepts of degeneracy and coloring number are frequently considered in the context of finite graphs, the original motivation for Erdős & Hajnal (1966) was the theory of infinite graphs. For an infinite graph G, one may define the coloring number analogously to the definition for finite graphs, as the smallest cardinal number α such that there exists a well-ordering of the vertices of G 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; Erdős & Hajnal (1966) state that, at the time of publication of their paper, it was already well known.

The degeneracy of random subsets of infinite lattices has been studied under the name of bootstrap percolation.

Notes

↑ Bader & Hogue (2003).
↑ Freuder (1982).
↑ Kirousis & Thilikos (1996).
↑ Erdős & Hajnal (1966).
↑ Irani (1994).
↑ Matula & Beck (1983).
↑ Lick & White (1970).
↑ Barabási & Albert (1999).
↑ Jensen & Toft (2011), p. 78: "It is easy to see that col(G) = Δ(G) + 1 if and only if G has a Δ(G)-regular component." In the notation used by Jensen and Toft, col(G) is the degeneracy plus one, and Δ(G) is the maximum vertex degree.
↑ Matula (1968); Lick & White (1970), Proposition 1, page 1084.
↑ Chrobak & Eppstein (1991).
↑ Seidman (1983).
↑ Bollobás (1984); Łuczak (1991);Dorogovtsev, Goltsev & Mendes (2006).
↑ Bader & Hogue (2003); Altaf-Ul-Amin et al. (2003); Wuchty & Almaas (2005).
↑ Gaertler & Patrignani (2004); Alvarez-Hamelin et al. (2006).
↑ Garcia-Algarra et al. (2017).
↑ Balogh et al. (2012).
↑ Kirkpatrick et al. (2002).
↑ Adler (1991).
↑ Chrobak & Eppstein (1991); Gabow & Westermann (1992); Venkateswaran (2004); Asahiro et al. (2006); Kowalik (2006).
↑ Dean, Hutchinson & Scheinerman (1991).
↑ Erdős & Hajnal (1966); Szekeres & Wilf (1968).
↑ Moody & White (2003).
↑ Robertson & Seymour (1984).
↑ Burr & Erdős (1975).
↑ 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.), Algorithms and Computation (Vol. 6506, pp. 403–414). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-17517-6_36

Related Research Articles

In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let $r$ and $s$ be any two positive integers. Ramsey's theorem states that there exists a least positive integer $R (r, s)$ for which every blue-red edge colouring of the complete graph on $R (r, s)$ vertices contains a blue clique on $r$ vertices or a red clique on $s$ vertices. (Here $R (r, s)$ signifies an integer that depends on both $r$ and $s$ .)

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph $is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.$

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

In graph theory, a critical graph is an undirected graph all of whose proper subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed in a graph coloring of the given graph. The decrease in the number of colors cannot be by more than one.

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In graph theory, the degree of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex $is denoted or . The maximum degree of a graph is denoted by, and is the maximum of's vertices' degrees. The minimum degree of a graph is denoted by, and is the minimum of's vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0.$

In graph theory, the Hadwiger number of an undirected graph $G$ is the size of the largest complete graph that can be obtained by contracting edges of $G$ . Equivalently, the Hadwiger number $h (G)$ is the largest number $n$ for which the complete graph $K n$ is a minor of $G$ , a smaller graph obtained from $G$ by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of $G$ or the homomorphism degree of $G$ . It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of $G$ .

The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is k-arboric.

In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph. The distinction of what constitutes a dense or sparse graph is ill-defined, and is often represented by 'roughly equal to' statements. Due to this, the way that density is defined often depends on the context of the problem.

In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the graph in sequence and assigns each vertex its first available color, using a vertex ordering chosen to use as many colors as possible. Grundy numbers are named after P. M. Grundy, who studied an analogous concept for directed graphs in 1939. The undirected version was introduced by Christen & Selkow (1979).

In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible.

András Hajnal was a professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics.

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with $colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős, after whom it is named.$

In graph theory, a mathematical discipline, coloring refers to an assignment of colours or labels to vertices, edges and faces of a graph. Defective coloring is a variant of proper vertex coloring. In a proper vertex coloring, the vertices are coloured such that no adjacent vertices have the same colour. In defective coloring, on the other hand, vertices are allowed to have neighbours of the same colour to a certain extent.

References

Adler, Joan (1991), "Bootstrap percolation", Physica A: Statistical Mechanics and its Applications , 171 (3): 453–470, Bibcode:1991PhyA..171..453A, doi:10.1016/0378-4371(91)90295-n
Altaf-Ul-Amin, M.; Nishikata, K.; Koma, T.; Miyasato, T.; Shinbo, Y.; Arifuzzaman, M.; Wada, C.; Maeda, M.; Oshima, T. (2003), "Prediction of protein functions based on $k$ -cores of protein-protein interaction networks and amino acid sequences" (PDF), Genome Informatics, 14: 498–499, archived from the original (PDF) on 2007-09-27
Alvarez-Hamelin, José Ignacio; Dall'Asta, Luca; Barrat, Alain; Vespignani, Alessandro (2006), " $k$ -core decomposition: a tool for the visualization of large scale networks", in Weiss, Yair; Schölkopf, Bernhard; Platt, John (eds.), Advances in Neural Information Processing Systems 18: Proceedings of the 2005 Conference, vol. 18, The MIT Press, p. 41, arXiv: cs/0504107 , Bibcode:2005cs........4107A, ISBN 0262232537
Asahiro, Yuichi; Miyano, Eiji; Ono, Hirotaka; Zenmyo, Kouhei (2006), "Graph orientation algorithms to minimize the maximum outdegree", CATS '06: Proceedings of the 12th Computing: The Australasian Theory Symposium, Darlinghurst, Australia, Australia: Australian Computer Society, Inc., pp. 11–20, ISBN 1-920682-33-3
Bader, Gary D.; Hogue, Christopher W. V. (2003), "An automated method for finding molecular complexes in large protein interaction networks", BMC Bioinformatics , 4 (1): 2, doi: 10.1186/1471-2105-4-2 , PMC 149346 , PMID 12525261
Balogh, József; Bollobás, Béla; Duminil-Copin, Hugo; Morris, Robert (2012), "The sharp threshold for bootstrap percolation in all dimensions", Transactions of the American Mathematical Society , 364 (5): 2667–2701, arXiv: 1010.3326 , doi:10.1090/S0002-9947-2011-05552-2, MR 2888224, S2CID 2708046
Barabási, Albert-László; Albert, Réka (1999), "Emergence of scaling in random networks" (PDF), Science , 286 (5439): 509–512, arXiv: cond-mat/9910332 , Bibcode:1999Sci...286..509B, doi:10.1126/science.286.5439.509, PMID 10521342, S2CID 524106, archived from the original (PDF) on 2006-11-11
Bollobás, Béla (1984), "The evolution of sparse graphs", Graph Theory and Combinatorics, Proc. Cambridge Combinatorial Conf. in honor of Paul Erdős, Academic Press, pp. 35–57
Burr, Stefan A.; Erdős, Paul (1975), "On the magnitude of generalized Ramsey numbers for graphs", Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. 1 (PDF), Colloq. Math. Soc. János Bolyai, vol. 10, Amsterdam: North-Holland, pp. 214–240, MR 0371701
Chrobak, Marek; Eppstein, David (1991), "Planar orientations with low out-degree and compaction of adjacency matrices" (PDF), Theoretical Computer Science , 86 (2): 243–266, doi: 10.1016/0304-3975(91)90020-3
Dean, Alice M.; Hutchinson, Joan P.; Scheinerman, Edward R. (1991), "On the thickness and arboricity of a graph", Journal of Combinatorial Theory , Series B, 52 (1): 147–151, doi:10.1016/0095-8956(91)90100-X, MR 1109429
Dorogovtsev, S. N.; Goltsev, A. V.; Mendes, J. F. F. (2006), " $k$ -core organization of complex networks", Physical Review Letters , 96 (4): 040601, arXiv: cond-mat/0509102 , Bibcode:2006PhRvL..96d0601D, doi:10.1103/PhysRevLett.96.040601, PMID 16486798, S2CID 2035
Erdős, Paul; Hajnal, András (1966), "On chromatic number of graphs and set-systems" (PDF), Acta Mathematica Hungarica , 17 (1–2): 61–99, doi: 10.1007/BF02020444 , MR 0193025
Freuder, Eugene C. (1982), "A sufficient condition for backtrack-free search", Journal of the ACM , 29 (1): 24–32, doi: 10.1145/322290.322292 , S2CID 8624975
Gabow, H. N.; Westermann, H. H. (1992), "Forests, frames, and games: algorithms for matroid sums and applications", Algorithmica , 7 (1): 465–497, doi:10.1007/BF01758774, S2CID 40358357
Gaertler, Marco; Patrignani, Maurizio (2004), "Dynamic analysis of the autonomous system graph", Proc. 2nd International Workshop on Inter-Domain Performance and Simulation (IPS 2004), pp. 13–24, CiteSeerX 10.1.1.81.6841
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 $k$ -core decomposition", PeerJ, 5: e3321, doi: 10.7717/peerj.3321 , PMC 5438587 , PMID 28533969
Irani, Sandy (1994), "Coloring inductive graphs on-line", Algorithmica , 11 (1): 53–72, doi:10.1007/BF01294263, S2CID 181800
Jensen, Tommy R.; Toft, Bjarne (2011), Graph Coloring Problems, Wiley Series in Discrete Mathematics and Optimization, vol. 39, John Wiley & Sons, ISBN 9781118030745
Kirkpatrick, Scott; Wilcke, Winfried W.; Garner, Robert B.; Huels, Harald (2002), "Percolation in dense storage arrays", Physica A: Statistical Mechanics and its Applications , 314 (1–4): 220–229, Bibcode:2002PhyA..314..220K, doi:10.1016/S0378-4371(02)01153-6, MR 1961703
Kirousis, L. M.; Thilikos, D. M. (1996), "The linkage of a graph" (PDF), SIAM Journal on Computing , 25 (3): 626–647, doi:10.1137/S0097539793255709, archived from the original (PDF) on 2011-07-21
Kowalik, Łukasz (2006), "Approximation scheme for lowest outdegree orientation and graph density measures", Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006), Lecture Notes in Computer Science, 4288, Springer-Verlag: 557–566, doi:10.1007/11940128_56, ISBN 978-3-540-49694-6
Lee, Choongbum (2017), "Ramsey numbers of degenerate graphs", Annals of Mathematics, 185 (3): 791–829, arXiv: 1505.04773 , doi:10.4007/annals.2017.185.3.2, S2CID 7974973
Lick, Don R.; White, Arthur T. (1970), " $k$ -degenerate graphs", Canadian Journal of Mathematics , 22 (5): 1082–1096, doi: 10.4153/CJM-1970-125-1
Łuczak, Tomasz (1991), "Size and connectivity of the $k$ -core of a random graph" (PDF), Discrete Mathematics , 91 (1): 61–68, doi: 10.1016/0012-365X(91)90162-U
Malliaros, Fragkiskos D.; Giatsidis, Christos; Papadopoulos, Apostolos N.; Vazirgiannis, Michalis (2019), "The core decomposition of networks: theory, algorithms and applications" (PDF), The VLDB Journal, 29: 61–92, doi:10.1007/s00778-019-00587-4, S2CID 85519668
Matula, David W. (1968), "A min-max theorem for graphs with application to graph coloring", SIAM 1968 National Meeting, SIAM Review , 10 (4): 481–482, doi:10.1137/1010115
Matula, David W.; Beck, L. L. (1983), "Smallest-last ordering and clustering and graph coloring algorithms", Journal of the ACM , 30 (3): 417–427, doi: 10.1145/2402.322385 , MR 0709826, S2CID 4417741
Moody, James; White, Douglas R. (2003), "Structural cohesion and embeddedness: a hierarchical conception of social groups", American Sociological Review , 68 (1): 1–25, doi:10.2307/3088904, JSTOR 3088904
Robertson, Neil; Seymour, Paul (1984), "Graph minors. III. Planar tree-width", Journal of Combinatorial Theory , Series B, 36 (1): 49–64, doi: 10.1016/0095-8956(84)90013-3
Seidman, Stephen B. (1983), "Network structure and minimum degree", Social Networks , 5 (3): 269–287, doi:10.1016/0378-8733(83)90028-X
Szekeres, George; Wilf, Herbert S. (1968), "An inequality for the chromatic number of a graph", Journal of Combinatorial Theory , 4: 1–3, doi: 10.1016/S0021-9800(68)80081-X
Venkateswaran, V. (2004), "Minimizing maximum indegree", Discrete Applied Mathematics , 143 (1–3): 374–378, doi: 10.1016/j.dam.2003.07.007
Wuchty, S.; Almaas, E. (2005), "Peeling the yeast protein network", Proteomics , 5 (2): 444–449, doi:10.1002/pmic.200400962, PMID 15627958, S2CID 17659720

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[FOOTNOTEBaderHogue2003-1] Bader & Hogue (2003).

[FOOTNOTEFreuder1982-2] Freuder (1982).

[FOOTNOTEKirousisThilikos1996-3] Kirousis & Thilikos (1996).

[FOOTNOTEErdősHajnal1966-4] Erdős & Hajnal (1966).

[FOOTNOTEIrani1994-5] Irani (1994).

[FOOTNOTEMatulaBeck1983-6] Matula & Beck (1983).

[7] Lick & White (1970).

[8] Barabási & Albert (1999).

[9] Jensen & Toft (2011), p. 78: "It is easy to see that col(G) = Δ(G) + 1 if and only if G has a Δ(G)-regular component." In the notation used by Jensen and Toft, col(G) is the degeneracy plus one, and Δ(G) is the maximum vertex degree.

[10] Matula (1968); Lick & White (1970), Proposition 1, page 1084.

[11] Chrobak & Eppstein (1991).

[12] Seidman (1983).

[13] Bollobás (1984); Łuczak (1991);Dorogovtsev, Goltsev & Mendes (2006).

[14] Bader & Hogue (2003); Altaf-Ul-Amin et al. (2003); Wuchty & Almaas (2005).

[15] Gaertler & Patrignani (2004); Alvarez-Hamelin et al. (2006).

[FOOTNOTEGarcia-AlgarraPastorIriondoGaleano2017-16] Garcia-Algarra et al. (2017).

[FOOTNOTEBaloghBollobásDuminil-CopinMorris2012-17] Balogh et al. (2012).

[FOOTNOTEKirkpatrickWilckeGarnerHuels2002-18] Kirkpatrick et al. (2002).

[FOOTNOTEAdler1991-19] Adler (1991).

[20] Chrobak & Eppstein (1991); Gabow & Westermann (1992); Venkateswaran (2004); Asahiro et al. (2006); Kowalik (2006).

[FOOTNOTEDeanHutchinsonScheinerman1991-21] Dean, Hutchinson & Scheinerman (1991).

[22] Erdős & Hajnal (1966); Szekeres & Wilf (1968).

[23] Moody & White (2003).

[24] Robertson & Seymour (1984).

[25] Burr & Erdős (1975).

[26] 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.), Algorithms and Computation (Vol. 6506, pp. 403–414). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-17517-6_36

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]