Given a graph $G$ with only even degrees, let $\varepsilon(G)$ denote the number of Eulerian orientations, and let $h(G)$ denote the number of half graphs, that is, subgraphs $F$ such that $d_F(v)=d_G(v)/2$ for each vertex $v$. Recently, Borbényi and Csikvári proved that $\varepsilon(G)\geq h(G)$ holds true for all Eulerian graphs, with equality if and only if $G$ is bipartite. In this paper we give a simple new proof of this fact, and we give identities and inequalities for the number of Eulerian orientations and half graphs of a $2$-cover of a graph $G$.
@article{10_37236_8767,
author = {P\'eter Csikv\'ari and Andr\'as Imolay},
title = {Covers, orientations and factors},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {3},
doi = {10.37236/8767},
zbl = {1445.05081},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8767/}
}
TY - JOUR
AU - Péter Csikvári
AU - András Imolay
TI - Covers, orientations and factors
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/8767/
DO - 10.37236/8767
ID - 10_37236_8767
ER -
%0 Journal Article
%A Péter Csikvári
%A András Imolay
%T Covers, orientations and factors
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/8767/
%R 10.37236/8767
%F 10_37236_8767
Péter Csikvári; András Imolay. Covers, orientations and factors. The electronic journal of combinatorics, Tome 27 (2020) no. 3. doi: 10.37236/8767
