Choosability of multipartite hypergraphs

2025/12/24 by Peter Bradshaw, Bradshaw, Peter, Abhishek Dhawan +7
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Complexity and Algorithms in Graphs #Advanced Graph Theory Research

paper · doi:10.48550/arxiv.2512.21222

Abstract

A k-uniform hypergraph (or k-graph) H = (V, E) is k-partite if V can be partitioned into k sets V₁, …, V_k such that each edge in E contains precisely one vertex from each V_i. We show that k-partite k-graphs of maximum degree Δ are q-choosable for q ≥ ((4)/(5)(k-1 + o(1))Δ/log Δ)^1/(k-1). Our proof yields an efficient randomized algorithm for finding such a coloring, which shows that the conjectured algorithmic barrier for coloring pseudorandom k-graphs does not apply to k-partite k-graphs.

Citations

• Toward Vu's conjecture
• The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
• List colorings of k-partite k-graphs
• Coloring graphs with forbidden almost bipartite subgraphs
• The chromatic number of triangle-free hypergraphs
• A simplified proof of the Johansson-Molloy Theorem using the Rosenfeld\n counting method
• Improved bounds for coloring locally sparse hypergraphs
• Graph structure via local occupancy
• Coloring sparse hypergraphs
• Independent sets in hypergraphs
• Coloring Simple Hypergraphs
• On colouring the nodes of a network

Related

• Choosability with separation of complete multipartite graphs and hypergraphs
• List colorings of k-partite k-graphs
• Choosability with Separation in Complete Multipartite Graphs
• Finding Partite Hypergraphs Efficiently
• Chromatic-choosability of hypergraphs with high chromatic number