Graph Coloring & Labeling

← Back to Domain-Specific Families

Abstractions about vertex and path colorings, graph labelings, bandwidth, queue number, monochromatic structure, and coloring existence theorems.

14 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.

• 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.
• Friendly-index set — Collect every edge-label imbalance attainable from nearly balanced binary vertex labelings of a graph, yielding a set-valued graph invariant rather than one selected labeling.
• 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.
• Graceful labeling — An injective vertex labeling from zero through the edge count whose absolute edge differences are exactly one through that count.
• Graph bandwidth — The minimum possible largest label distance across an edge when a graph’s vertices are placed at distinct positions on a line.
• Greedy coloring — A sequential graph-coloring algorithm that assigns each vertex the first available color not used by already colored neighbors.
• Hosoya Index — Count every matching of a graph, including the empty matching, to obtain a graph invariant used in matching theory and as a molecular topological descriptor.
• 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.
• Queue number — The minimum number of edge queues needed in a vertex ordering of a graph so no two edges in the same queue are properly nested.
• 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.
• Well-colored graph — A graph for which greedy vertex coloring uses the chromatic number of colors under every vertex ordering.