Imbalance conjecture

Importance: Medium ✭✭
Author(s): Kozerenko, Sergiy
Subject: Graph Theory
Recomm. for undergrads: no
Posted by: Sergiy Kozerenko
on: September 24th, 2013

\begin{conjecture} Suppose that for all edges $e\in E(G)$ we have $imb(e)>0$. Then $M_{G}$ is graphic. \end{conjecture}

Consider simple undirected graph $G$ and let $e=uv\in E(G)$.

The \emph{imbalance} of the edge $e$ defined as $imb(e)=|deg(u)-deg(v)|$.

The multiset of all edge imbalances of $G$ is denoted by $M_{G}$.

Note, that conjecture is verified for all such graphs with $\leq 9$ vertices.


*\href [Graphs with graphic imbalance sequences]{}

* indicates original appearance(s) of problem.