Hall

Python components for calculating Hall inequalities.

AUTHORS:

• Matthew Henderson (2010-12-30): initial version

hall_inequality(graph, list_assignment, colours)

Decide whether the Hall inequality for graph is satisfied

hall_inequality_induced_by(graph, list_assignment, colours, vertices)

Check Hall’s inequality for a subgraph of ‘graph’ induced by ‘vertices’.

hall_number(graph, list_assignment, colour)

Compute the independence number of the subgraph induced by those vertices in ‘graph’ having ‘colour’ in their list. Not to be confused with Hall number in the literature.

hall_sum(graph, list_assignment, colours)

Sum Hall numbers over all monochromatic subgraphs.

halls_condition(graph, list_assignment, colours)

Check Hall’s condition.

halls_condition_restricted_to(graph, list_assignment, colours, node_subsets)

Check Hall’s condition restricted to subgraphs induced by node_subsets.