Hall’s Multicoloring Condition and Common Partial Systems of Distinct Representatives

If \(L\) is a list assignment function and \(\kappa\) is a multiplicity function on the vertices of a graph \(G\), a certain condition on \((G, L, \kappa)\), known as Hall’s multicoloring condition, is obviously necessary for the existence of a multicoloring of the vertices of \(G\). A graph \(G\) is said to be in the class \(MHC\) if it has a multicoloring for any functions \(L\) and \(\kappa\) such that \((G, L, \kappa)\) satisfies Hall’s multicoloring condition. It is known that if \(G\) is in \(MHC\) then each block of \(G\) is a clique and each cutpoint lies in precisely two blocks. We conjecture that the converse is true as well. It is also known that if \(G\) is a graph consisting of two cliques joined at a point then \(G\) is in \(MHC\). We present a new proof of this result which uses common partial systems of distinct representatives, the relationship between matching number and vertex covering number for 3-partite hypergraphs, and Menger’s Theorem.