Graph cannot be colored with

Error message

Graph cannot be colored with {numColors} color(s). A larger number of colors may be required.

What it means

ColorGraph performs exhaustive backtracking; if no assignment of numColors colors produces a proper coloring (starting from vertex 0), it concludes the graph's chromatic number exceeds numColors and throws ArgumentException advising a larger color count.

Solutions

Increase numColors (e.g. start with the graph's max degree + 1 and retry).
Detect the minimum needed colors iteratively: try k = 1, 2, 3, ... catching ArgumentException until success.
Pre-analyze the graph (clique size, bipartiteness) to pick a sufficient k.

Example fix

// before
var colors = solver.ColorGraph(matrix, 2); // odd cycle: fails
// after
int[] colors = null;
for (var k = 1; k <= matrix.GetLength(0); k++)
{
    try { colors = solver.ColorGraph(matrix, k); break; }
    catch (ArgumentException) { }
}

Defensive patterns

Strategy: try-catch

Validate before calling

// Heuristic lower bound: max degree + 1 often suffices
var k = Enumerable.Range(0, matrix.GetLength(0)).Max(v => CountRow(matrix, v)) + 1;

Try / catch

try { colors = solver.ColorGraph(matrix, k); }
catch (ArgumentException) { colors = solver.ColorGraph(matrix, k + 1); } // or retry loop

Prevention

Estimate chromatic number before choosing k
Prefer incremental k with retry over fixed guesses
Remember odd cycles need 3 colors, cliques need their size

When it happens

Trigger: Coloring a bipartite graph with 1 color, an odd cycle with 2 colors, or any graph whose chromatic number is greater than the supplied numColors.

Common situations: Underestimating required colors for dense graphs (cliques), scheduling conflicts modeled as graphs where k was set from a fixed constant, test scenarios asserting infeasibility.

Understand the failure class

Background: "Must be a positive integer", "Invalid value", "Unsupported": the invalid-argument-value error family, when a library rejects the value you pass — this error's family across 35 libraries.

Related errors

AI-assisted analysis of TheAlgorithms/C-Sharp@96e2905cab (2026-09-13). Data as JSON: /api/errors/8282aa4cb1e10bc5. Report an issue: GitHub.

Appendix: source

Thrown at Algorithms/Problems/GraphColoring/GraphColoringSolver.cs:99

        if (numColors <= 0)
        {
            throw new ArgumentException("Number of colors must be positive.", nameof(numColors));
        }

        // Handle empty graph
        if (numVertices == 0)
        {
            return Array.Empty<int>();
        }

        var colors = new int[numVertices];

        // Initialize all vertices as uncolored (-1)
        Array.Fill(colors, -1);

        if (!ColorVertex(adjacencyMatrix, colors, 0, numColors))
        {
            throw new ArgumentException(
                $"Graph cannot be colored with {numColors} color(s). " +
                $"A larger number of colors may be required.");
        }

        return colors;
    }

    /// <summary>
    /// Recursively attempts to color vertices using backtracking.
    /// </summary>
    /// <param name="adjacencyMatrix">The graph adjacency matrix.</param>
    /// <param name="colors">Current color assignment for each vertex.</param>
    /// <param name="vertex">The current vertex to color.</param>
    /// <param name="numColors">The number of available colors.</param>
    /// <returns><c>true</c> if a valid coloring is found; otherwise, <c>false</c>.</returns>
    /// <remarks>
    /// This method tries each available color for the current vertex. If a color is valid
    /// (doesn't conflict with adjacent vertices), it proceeds to color the next vertex.

View on GitHub (pinned to 96e2905cab)