Advanced Coloring Invariants API

Advanced Coloring Invariants

The advanced_colorings module contains solver-based routines for several specialized coloring parameters, including open-neighborhood conflict-free colorings, open-neighborhood odd colorings, and rainbow connection colorings.

class graphcalc.graphs.invariants.advanced_colorings.EdgeColoringSolveResult(feasible: bool, coloring: Dict[Tuple[Hashable, Hashable], int] | None = None)

Bases: object

Result of an edge-coloring feasibility computation.

Parameters:

• feasible (bool) – Whether a feasible coloring satisfying the requested constraints exists.

• coloring (dict, optional) – A witness edge-coloring when one is found. Each key is an undirected edge represented by a normalized 2-tuple, and each value is a positive integer color label.

coloring: Dict[Tuple[Hashable, Hashable], int] | None = None

feasible: bool

class graphcalc.graphs.invariants.advanced_colorings.SolveResult(feasible: bool, coloring: Dict[Hashable, int] | None = None)

Bases: object

Result of a coloring feasibility computation.

Parameters:

• feasible (bool) – Whether a feasible coloring satisfying the requested constraints exists.

• coloring (dict, optional) – A witness coloring when one is found. The dictionary maps each vertex to a positive integer color label.

coloring: Dict[Hashable, int] | None = None

feasible: bool

graphcalc.graphs.invariants.advanced_colorings.has_open_neighborhood_conflict_free_coloring(G: Graph, k: int, **solver_kwargs) → bool

Decide whether a graph admits an open-neighborhood conflict-free coloring with k colors.

A vertex coloring \(\varphi : V(G) \to \{1,\dots,k\}\) is called an open-neighborhood conflict-free coloring if, for every non-isolated vertex \(v\), there exists a color appearing exactly once in the open neighborhood \(N(v)\).

Unlike proper colorings, adjacent vertices are allowed to receive the same color.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected simple graph.

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

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Optional solver specification handled by graphcalc.solvers.with_solver().

• solver_options (dict, optional) – Extra options for the solver backend.

• verbose (bool, default=False) – If True, show solver output when supported.

Returns:

True if such a coloring exists, and False otherwise.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(3)
>>> gc.has_open_neighborhood_conflict_free_coloring(G, 2)
True

graphcalc.graphs.invariants.advanced_colorings.has_open_neighborhood_odd_coloring(G: Graph, k: int, **solver_kwargs) → bool

Decide whether a graph admits an open-neighborhood odd coloring with k colors.

A vertex coloring \(\varphi : V(G) \to \{1,\dots,k\}\) is an open-neighborhood odd coloring if:

• adjacent vertices receive different colors, and

• for every non-isolated vertex \(v\), there exists a color whose frequency in \(N(v)\) is odd.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected simple graph.

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

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Optional solver specification handled by graphcalc.solvers.with_solver().

• solver_options (dict, optional) – Extra options for the solver backend.

• verbose (bool, default=False) – If True, show solver output when supported.

Returns:

True if such a coloring exists, and False otherwise.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(3)
>>> gc.has_open_neighborhood_odd_coloring(G, 2)
False

graphcalc.graphs.invariants.advanced_colorings.has_proper_open_neighborhood_conflict_free_coloring(G: Graph, k: int, **solver_kwargs) → bool

Decide whether a graph admits a proper open-neighborhood conflict-free coloring with k colors.

A vertex coloring \(\varphi : V(G) \to \{1,\dots,k\}\) is a proper open-neighborhood conflict-free coloring if:

• adjacent vertices receive different colors, and

• for every non-isolated vertex \(v\), some color appears exactly once in the open neighborhood \(N(v)\).

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected simple graph.

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

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Optional solver specification handled by graphcalc.solvers.with_solver().

• solver_options (dict, optional) – Extra options for the solver backend.

• verbose (bool, default=False) – If True, show solver output when supported.

Returns:

True if such a coloring exists, and False otherwise.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(3)
>>> gc.has_proper_open_neighborhood_conflict_free_coloring(G, 2)
False

graphcalc.graphs.invariants.advanced_colorings.has_rainbow_connection_coloring(G: Graph, k: int, *, path_cutoff: int | None = None, **solver_kwargs) → bool

Decide whether a connected graph admits a rainbow connection coloring with k edge colors.

An edge-coloring of a connected graph \(G\) is a rainbow connection coloring if every pair of distinct vertices is joined by a path whose edges have pairwise distinct colors. The minimum such number of colors is the rainbow connection number, denoted \(\mathrm{rc}(G)\).

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected simple graph.

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

• path_cutoff (int, optional) – Upper bound on the length of simple paths enumerated during the exact feasibility search. If omitted, paths are enumerated up to length \(|V(G)|-1\).

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Optional solver specification handled by graphcalc.solvers.with_solver().

• solver_options (dict, optional) – Extra options for the solver backend.

• verbose (bool, default=False) – If True, show solver output when supported.

Returns:

True if such an edge-coloring exists, and False otherwise.

Return type:

bool

Notes

This implementation is exact and MILP-based, but path enumeration may become expensive on larger graphs.

graphcalc.graphs.invariants.advanced_colorings.has_strong_rainbow_connection_coloring(G: Graph, k: int, **solver_kwargs) → bool

Decide whether a connected graph admits a strong rainbow connection coloring with k edge colors.

An edge-coloring of a connected graph \(G\) is a strong rainbow connection coloring if every pair of distinct vertices is joined by a rainbow shortest path. The minimum such number of colors is the strong rainbow connection number, denoted \(\mathrm{src}(G)\).

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected simple graph.

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

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Optional solver specification handled by graphcalc.solvers.with_solver().

• solver_options (dict, optional) – Extra options for the solver backend.

• verbose (bool, default=False) – If True, show solver output when supported.

Returns:

True if such an edge-coloring exists, and False otherwise.

Return type:

bool

Notes

This implementation is exact and MILP-based.

graphcalc.graphs.invariants.advanced_colorings.open_neighborhood_conflict_free_chromatic_number(G: Graph, k_max: int | None = None, **solver_kwargs) → int

Compute the open-neighborhood conflict-free chromatic number of a graph.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected simple graph.

• k_max (int, optional) – Upper bound on the number of colors tested. If omitted, uses \(|V(G)|\).

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Optional solver specification handled by graphcalc.solvers.with_solver().

• solver_options (dict, optional) – Extra options for the solver backend.

• verbose (bool, default=False) – If True, show solver output when supported.

Returns:

The minimum number of colors required.

Return type:

int

graphcalc.graphs.invariants.advanced_colorings.open_neighborhood_conflict_free_coloring(G: Graph, k: int, **solver_kwargs) → Dict[Hashable, int]

Return an open-neighborhood conflict-free coloring using k colors.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected simple graph.

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

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Optional solver specification handled by graphcalc.solvers.with_solver().

• solver_options (dict, optional) – Extra options for the solver backend.

• verbose (bool, default=False) – If True, show solver output when supported.

Returns:

A dictionary mapping each vertex of \(G\) to a color in {1,\dots,k}.

Return type:

dict

Raises:

ValueError – If no feasible coloring exists with k colors.

graphcalc.graphs.invariants.advanced_colorings.open_neighborhood_odd_chromatic_number(G: Graph, k_max: int | None = None, **solver_kwargs) → int

Compute the open-neighborhood odd chromatic number of a graph.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected simple graph.

• k_max (int, optional) – Upper bound on the number of colors tested. If omitted, uses \(|V(G)|\).

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Optional solver specification handled by graphcalc.solvers.with_solver().

• solver_options (dict, optional) – Extra options for the solver backend.

• verbose (bool, default=False) – If True, show solver output when supported.

Returns:

The minimum number of colors required.

Return type:

int

graphcalc.graphs.invariants.advanced_colorings.open_neighborhood_odd_coloring(G: Graph, k: int, **solver_kwargs) → Dict[Hashable, int]

Return an open-neighborhood odd coloring using k colors.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected simple graph.

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

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Optional solver specification handled by graphcalc.solvers.with_solver().

• solver_options (dict, optional) – Extra options for the solver backend.

• verbose (bool, default=False) – If True, show solver output when supported.

Returns:

A dictionary mapping each vertex of \(G\) to a color in {1,\dots,k}.

Return type:

dict

Raises:

ValueError – If no feasible coloring exists with k colors.

graphcalc.graphs.invariants.advanced_colorings.proper_open_neighborhood_conflict_free_chromatic_number(G: Graph, k_max: int | None = None, **solver_kwargs) → int

Compute the proper open-neighborhood conflict-free chromatic number of a graph.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected simple graph.

• k_max (int, optional) – Upper bound on the number of colors tested. If omitted, uses \(|V(G)|\).

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Optional solver specification handled by graphcalc.solvers.with_solver().

• solver_options (dict, optional) – Extra options for the solver backend.

• verbose (bool, default=False) – If True, show solver output when supported.

Returns:

The minimum number of colors required.

Return type:

int

graphcalc.graphs.invariants.advanced_colorings.proper_open_neighborhood_conflict_free_coloring(G: Graph, k: int, **solver_kwargs) → Dict[Hashable, int]

Return a proper open-neighborhood conflict-free coloring using k colors.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected simple graph.

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

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Optional solver specification handled by graphcalc.solvers.with_solver().

• solver_options (dict, optional) – Extra options for the solver backend.

• verbose (bool, default=False) – If True, show solver output when supported.

Returns:

A dictionary mapping each vertex of \(G\) to a color in {1,\dots,k}.

Return type:

dict

Raises:

ValueError – If no feasible coloring exists with k colors.

graphcalc.graphs.invariants.advanced_colorings.rainbow_connection_coloring(G: Graph, k: int, *, path_cutoff: int | None = None, **solver_kwargs) → Dict[Tuple[Hashable, Hashable], int]

Return a rainbow connection edge-coloring using k colors.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – A connected undirected simple graph.

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

• path_cutoff (int, optional) – Upper bound on the length of simple paths enumerated during the exact feasibility search.

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Optional solver specification handled by graphcalc.solvers.with_solver().

• solver_options (dict, optional) – Extra options for the solver backend.

• verbose (bool, default=False) – If True, show solver output when supported.

Returns:

A dictionary mapping each undirected edge of \(G\) to a color in {1,\dots,k}.

Return type:

dict

Raises:

ValueError – If G is disconnected or no feasible coloring exists with k colors.

graphcalc.graphs.invariants.advanced_colorings.rainbow_connection_number(G: Graph, *, k_max: int | None = None, path_cutoff: int | None = None, **solver_kwargs) → int

Compute the rainbow connection number of a connected graph.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – A connected undirected simple graph.

• k_max (int, optional) – Upper bound on the number of colors tested. If omitted, uses \(|E(G)|\).

• path_cutoff (int, optional) – Upper bound on the length of simple paths enumerated during the exact feasibility search.

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Optional solver specification handled by graphcalc.solvers.with_solver().

• solver_options (dict, optional) – Extra options for the solver backend.

• verbose (bool, default=False) – If True, show solver output when supported.

Returns:

The rainbow connection number \(\mathrm{rc}(G)\).

Return type:

int

Raises:

ValueError – If G is disconnected.

graphcalc.graphs.invariants.advanced_colorings.strong_rainbow_connection_coloring(G: Graph, k: int, **solver_kwargs) → Dict[Tuple[Hashable, Hashable], int]

Return a strong rainbow connection edge-coloring using k colors.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – A connected undirected simple graph.

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

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Optional solver specification handled by graphcalc.solvers.with_solver().

• solver_options (dict, optional) – Extra options for the solver backend.

• verbose (bool, default=False) – If True, show solver output when supported.

Returns:

A dictionary mapping each undirected edge of \(G\) to a color in {1,\dots,k}.

Return type:

dict

Raises:

ValueError – If G is disconnected or no feasible coloring exists with k colors.

graphcalc.graphs.invariants.advanced_colorings.strong_rainbow_connection_number(G: Graph, *, k_max: int | None = None, **solver_kwargs) → int

Compute the strong rainbow connection number of a connected graph.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – A connected undirected simple graph.

• k_max (int, optional) – Upper bound on the number of colors tested. If omitted, uses \(|E(G)|\).

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Optional solver specification handled by graphcalc.solvers.with_solver().

• solver_options (dict, optional) – Extra options for the solver backend.

• verbose (bool, default=False) – If True, show solver output when supported.

Returns:

The strong rainbow connection number \(\mathrm{src}(G)\).

Return type:

int

Raises:

ValueError – If G is disconnected.