Michaela Borzechowski,Simon Weber
Michaela Borzechowski
A unique sink orientation (USO) is an orientation of the n-dimensional hypercube graph such that every non-empty face contains a unique sink. We consider the only known connected flip graph on USOs. This flip graph is based on the following...
Dömötör Pálvölgyi
Dömötör Pálvölgyi
We exhibit a 5-uniform hypergraph that has no polychromatic 3-coloring, but all its restricted subhypergraphs with edges of size at least 3 are 2-colorable. This disproves a bold conjecture of Keszegh and the author, and can be considered a...
Oswin Aichholzer,Lukas Andritsch,Karin Baur et al.
Oswin Aichholzer et al.
We derive a simple bijection between geometric plane perfect matchings on 2n points in convex position and triangulations on n + 2 points in convex position. We then extend this bijection to monochromatic plane perfect matchings on periodi...
Gábor Bacsó,Csilla Bujtás,Casey Tompkins et al.
Gábor Bacsó et al.
A paired-dominating set of a graph G is a dominating set D with the additional requirement that the induced subgraph G[D] contains a perfect matching. We prove that the vertex set of every claw-free cubic graph can be partitioned into two p...