17 notes
Reference material: set theory and relations, proof techniques, linear algebra for graph theory, probability review, algorithms and complexity, mathematical notation, historical development, common graph families, theorem index, and symbol index.
Bipartite, complete, and regular graphs, interval and chordal graphs, comparability and perfect graphs, tournaments, grid graphs, De Bruijn graphs, Kneser graphs, the Petersen graph, and Ramanujan graphs.
Social networks, web graphs, PageRank, biological and chemical networks, electrical and transportation networks, compiler graphs, knowledge graphs, recommendation systems, graph neural networks, distributed systems, and blockchain networks.
Extremal graph theory, Turán-type problems, Szemerédi regularity lemma, minor theory, Robertson-Seymour theory, infinite graphs, topological and category-theoretic graph theory, simplicial complexes, graph limits, temporal graphs, and quantum graph theory.
Complexity classes, NP-complete graph problems, Hamiltonian paths and cycles, the traveling salesman problem, graph isomorphism, parameterized complexity, fixed-parameter tractability, and approximation hardness.
Graph traversal, BFS, DFS, shortest paths, Dijkstra, Bellman-Ford, Floyd-Warshall, network flow, maximum flow, minimum cut, matching algorithms, union-find, dynamic graph algorithms, approximation, and randomized algorithms.
Random graph models, Erdős-Rényi graphs, threshold phenomena, small-world and scale-free networks, preferential attachment, percolation, probabilistic methods, and random processes on networks.
Adjacency, incidence, and Laplacian matrices, graph spectrum, eigenvalues and eigenvectors, spectral theorems, algebraic connectivity, expander graphs, graph energy, Cayley graphs, and automorphism groups.
Vertex and edge coloring, chromatic number, chromatic polynomial, greedy coloring, Brooks' theorem, perfect graphs, Ramsey theory, list coloring, and fractional coloring.
Matchings, perfect matchings, Hall's marriage theorem, bipartite matching, maximum matching algorithms, vertex and edge covers, independent sets, cliques, and dominating sets.
Vertex and edge connectivity, cuts, bridges, articulation points, Menger's theorem, network reliability, expanders, separators, and random walks on graphs.
Planar graphs, plane embeddings, Euler's formula, faces, Kuratowski's theorem, coloring of planar graphs, dual graphs, geometric graphs, and connections to computational geometry.
Trees, forests, rooted and binary trees, spanning trees, minimum spanning trees, Prüfer sequences, tree traversal, tree decomposition, and applications of trees.
Directed graphs, in-degree and out-degree, directed paths and cycles, strong connectivity, DAGs, topological ordering, weighted graphs, multigraphs, hypergraphs, and labeled graphs.
A comprehensive reference covering graph theory from elementary definitions through structural theory, algorithms, algebraic methods, probabilistic models, computational complexity, and modern applications in fourteen parts with appendices.
Basic definitions, vertices and edges, graph representations, degree, walks, paths, cycles, connectivity, isomorphism, subgraphs, and classes of graphs — the bedrock of graph theory.
Counting, arrangement, structure, and extremal behavior of finite and discrete systems.