import { TestEdge, TestGraph, TestNode } from '../generation/generators/types';
import { PropertyValidationResult } from './types';
/**
 * Validate k-colorable property of a graph.
 * A graph is k-colorable if its vertices can be colored with k colors
 * such that no two adjacent vertices share the same color.
 *
 * This function uses a greedy coloring algorithm as an upper bound,
 * which gives us an approximation of the chromatic number χ(G).
 * If greedy uses > k colors, the graph is definitely not k-colorable.
 * If greedy uses ≤ k colors, we verify the coloring is valid.
 *
 * @param graph - The test graph to validate
 * @returns PropertyValidationResult with k-colorable validation
 */
export declare const validateKColorable: (graph: TestGraph) => PropertyValidationResult;
/**
 * Greedy graph coloring algorithm.
 * Assigns colors to vertices sequentially, always using the smallest
 * available color that doesn't conflict with already-colored neighbors.
 *
 * This is an approximation algorithm that uses at most Δ(G) + 1 colors,
 * where Δ(G) is the maximum degree of the graph. The actual chromatic
 * number χ(G) may be smaller.
 *
 * Time complexity: O(V + E) where V = vertices, E = edges
 * Space complexity: O(V) for color storage
 *
 * @param nodes - Array of graph nodes
 * @param edges - Array of graph edges
 * @param directed - Whether the graph is directed
 * @returns Map of node ID to color (0-indexed)
 */
export declare const greedyColoring: (nodes: TestNode[], edges: TestEdge[], directed: boolean) => Map<string, number>;
//# sourceMappingURL=coloring-validator.d.ts.map