Graph Coloring & Invariants

← Back to Domain-Specific Families

Abstractions about assigning labels or values to graph structures, spanning vertex- and edge-coloring schemes (equitable, exact, greedy, and rainbow coloring), coloring-related graph polynomials and invariants (chromatic polynomial, chromatic symmetric function, Wiener index), and special coloring problems (conflict-free coloring, monochromatic triangle, snark).

18 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Chromatic polynomial — A graph polynomial P(G,k) whose value at each nonnegative integer k counts the proper vertex colorings of graph G using k labeled colors.
• Chromatic symmetric function — A symmetric-function graph invariant formed as the weight-generating function of all proper vertex colorings by positive integers.
• Colin de Verdière graph invariant — A minor-monotone graph parameter defined by the maximum corank of a constrained symmetric matrix with one negative eigenvalue and the Strong Arnold property.
• Conductance (graph theory) — A normalized bottleneck measure comparing the edge flow leaving a vertex set with the smaller stationary volume of that set and its complement.
• Conflict-free coloring — A hypergraph vertex coloring in which every hyperedge contains at least one vertex whose color occurs exactly once within that edge.
• Equitable coloring — A proper vertex coloring whose color classes differ in size by at most one, combining adjacency separation with balanced allocation.
• Exact coloring — A proper vertex coloring in which each unordered pair of distinct colors occurs on exactly one edge.
• Gallai–Hasse–Roy–Vitaver theorem — A graph-theoretic duality stating that a graph's chromatic number equals one plus the minimum, over all edge orientations, of the longest directed-path length.
• Greedy coloring — A sequential graph-coloring algorithm that assigns each vertex the first available color not used by already colored neighbors.
• Integral graph — A finite graph whose adjacency matrix has only integer eigenvalues.
• Monochromatic triangle — The graph decision problem of coloring or partitioning edges with a fixed number of colors so that no triangle has all three edges of one color.
• Path coloring — An assignment of colors to specified graph paths so any two paths sharing an edge receive different colors, commonly modeling wavelength allocation in optical networks.
• Quantum graph — A metric graph equipped with differential operators on its edges and vertex boundary conditions that couple edgewise wavefunctions.
• Rainbow coloring — An edge coloring of a connected graph in which every pair of vertices is joined by a path whose edges all have distinct colors.
• Randić index — A graph invariant summing the reciprocal square root of endpoint-degree products over all edges, widely used as a molecular connectivity descriptor.
• Snark (graph theory) — A connected cubic graph whose edges cannot be properly colored with three colors, usually restricted by girth and nontrivial connectivity conditions.
• Well-colored graph — A graph for which greedy vertex coloring uses the chromatic number of colors under every vertex ordering.
• Wiener index — The sum of shortest-path distances over all unordered vertex pairs of a connected graph.