Auxiliary matching construction for hypergraph edge colouring
ID: auxiliary-matching-construction-for-hypergraph-edge-colouring
Given an -uniform hypergraph and colours, construct an -uniform auxiliary hypergraph with one task vertex for every and one resource vertex for every original vertex and colour. The assignment edge for contains the task and all resources with . A matching in a hypergraph of assignments is exactly a proper partial edge colouring. Task degrees are ; resource degrees are . Pairwise auxiliary hypergraph codegrees are at most . Thus nearly equal original degrees and small original hypergraph codegrees transfer to the setting of a Rödl nibble. A locally balanced Rödl nibble must control the unmatched task count in every original star, not merely the total uncovered proportion.
New to topics? Read the docs here!