coloring predicates

Coloring Predicates

graphcalc.graphs.invariants.coloring_predicates.can_edge_color_with_k(G, k)[source]

Decide whether \(G\) admits a proper edge-coloring with at most k colors.

A proper edge-coloring is a map \(c : E(G)\to\{0,1,\dots,k-1\}\) such that any two edges sharing an endpoint receive different colors. Equivalently, c is a proper vertex-coloring of the line graph \(L(G)\).

This routine uses simple backtracking and is intended only for small graphs.

Parameters:

  • G (networkx.Graph) – The input graph (intended for undirected simple graphs).

  • k (int) – The number of available colors.

Notes

  • Necessary condition: k >= Δ(G) for any graph with at least one edge. This is checked for early rejection.

  • The implementation searches edges in a heuristic order (edges incident to higher-degree vertices first).

  • This is a decision procedure; it does not return a coloring.

Conventions: - If k <= 0, returns False. - If |E(G)| = 0, returns True (empty coloring).

Complexity

Exponential in \(|E(G)|\) in the worst case. Intended only for small graphs.

returns:

True iff \(G\) has a proper edge-coloring using at most k colors.

rtype:

bool

graphcalc.graphs.invariants.coloring_predicates.is_class1(G, max_edges=40)[source]

Test whether a simple graph is Class 1 (edge-chromatic number equals maximum degree).

For a simple undirected graph \(G\), the edge-chromatic number \(\chi'(G)\) is the minimum number of colors in a proper edge-coloring. The graph is:

  • Class 1 if \(\chi'(G) = \Delta(G)\),

  • Class 2 if \(\chi'(G) = \Delta(G) + 1\).

By Vizing’s Theorem, every simple graph satisfies \(\chi'(G) \in \{\Delta(G), \Delta(G)+1\}\).

This function decides Class 1 by: 1. Returning True for bipartite graphs (Kőnig’s line coloring theorem), and 2. Otherwise running an exact backtracking test for a \(\Delta(G)\)-edge-coloring.

Parameters:

  • G (networkx.Graph) – The input graph. Must be an undirected simple graph (nx.Graph).

  • max_edges (int, default=40) – Safety cutoff to avoid exponential blowups in backtracking.

Notes

  • If |E(G)| = 0 then \(\chi'(G)=\Delta(G)=0\), so \(G\) is Class 1.

  • Bipartite graphs satisfy \(\chi'(G)=\Delta(G)\).

Returns:

True iff \(G\) is Class 1, i.e., \(\chi'(G) = \Delta(G)\).

Return type:

bool

Raises:

ValueError – If G is not a simple undirected graph, or if |E(G)| > max_edges.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> # All bipartite graphs are class 1
>>> G = nx.cycle_graph(4)
>>> gc.is_class1(G)
True

>>> # The Petersen graph is class 2
>>> H = gc.petersen_graph()
>>> gc.is_class1(H)
False
graphcalc.graphs.invariants.coloring_predicates.is_class2(G, max_edges=40)[source]

Test whether a simple graph is Class 2 (edge-chromatic number equals \(\Delta(G)+1\)).

For simple graphs, Vizing’s theorem implies: \(G\) is Class 2 if and only if \(G\) is not Class 1.

Parameters:

  • G (networkx.Graph) – The input graph. Must be an undirected simple graph (nx.Graph).

  • max_edges (int, default=40) – Passed through to is_class1() for the backtracking cutoff.

Returns:

True iff \(G\) is Class 2, i.e., \(\chi'(G) = \Delta(G) + 1\).

Return type:

bool

Raises:

ValueError – If G is not a simple undirected graph, or if |E(G)| > max_edges.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> # All bipartite graphs are class 1
>>> G = nx.cycle_graph(4)
>>> gc.is_class2(G)
False

>>> # The Petersen graph is class 2
>>> H = gc.petersen_graph()
>>> gc.is_class2(H)
True