• ### Colorings v.s. list colorings of uniform hypergraphs(1804.02852)

April 9, 2018 math.CO
Let $r$ be an integer with $r\ge 2$ and $G$ be a connected $r$-uniform hypergraph with $m$ edges. By refining the broken cycle theorem for hypergraphs, we show that if $k>\frac{m-1}{\ln(1+\sqrt{2})}\approx 1.135 (m-1)$ then the $k$-list assignment of $G$ admitting the fewest colorings is the constant list assignment. This extends the previous results of Donner, Thomassen and the current authors for graphs.
• ### Inclusion-exclusion by ordering-free cancellation(1801.04706)

Jan. 15, 2018 math.CO
Whitney's broken circuit theorem gives a graphical example to reduce the number of the terms in the sum of the inclusion-exclusion formula by a predicted cancellation. So far, the known cancellations for the formula strongly depend on the prescribed (linear or partial) ordering on the index set. We give a new cancellation method, which does not require any ordering on the index set. Our method extends all the ordering-based' methods known in the literatures and in general reduces more terms. As examples, we use our method to improve some relevant results on graph polynomials.
• ### Flip-distance between \alpha-orientations of graphs embedded on plane and sphere(1706.00970)

June 3, 2017 math.CO
Felsner introduced a cycle reversal, namely the flip' reversal, for \alpha-orientations (i.e., each vertex admits a prescribed out-degree) of a graph G embedded on the plane and further proved that the set of all the \alpha-orientations of G carries a distributive lattice with respect to the flip reversals. In this paper, we give an explicit formula for the minimum number of flips needed to transform one \alpha-orientation into another for graphs embedded on the plane or sphere, respectively.