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

Abstract

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.