Graph-theory open problems

Imbalance conjecture

Medium ★★ Graph Theory
Author: Kozerenko, Sergiy— posted by Sergiy Kozerenko on 2013-09-24

Status partial high confidence

The imbalance conjecture remains open. Partial results confirm that $M_G$ is graphic for trees, unicyclic graphs, antiregular graphs, complete extensions of paths/cycles/complete graphs, and several classes of block graphs. The most recent work (Kozerenko–Serdiuk, Opuscula Math. 2023) substantially extends this list but does not resolve the general conjecture.

Cited literature (2)

  • partial Edge Imbalance Sequences And Their Graphicness (2019)
    Sergiy Kozerenko · Journal of Advanced Mathematical Studies

    Proves that certain unary and binary graph operations preserve graphicness of imbalance sequences, and discusses several conjectures related to graphicness, including connections between them.

  • partial New results on imbalance graphic graphs (2023)
    Sergiy Kozerenko, Andrii Serdiuk · Opuscula Mathematica · doi:10.7494/OpMath.2023.43.1.81

    Establishes imbalance graphicness for unicyclic graphs, antiregular graphs, and three classes of block graphs, extending earlier results but leaving the general conjecture open.

Reviewer notes. The original OPG bibliography paper 'On graphs with graphic imbalance sequences' (Kozerenko–Skochko, Algebra Discrete Math. 2014) is the starting-point reference and is excluded from since_posted. No counterexample has been found; the conjecture has been verified for all graphs with ≤9 vertices. No arXiv preprints specifically about the main imbalance conjecture were found. The 2019 paper's DOI could not be confirmed from the KSE publications page alone.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 07) (web search enabled).

Conjecture. Suppose that for all edges $ e\in E(G) $ we have $ imb(e)>0 $ . Then $ M_{G} $ is graphic.
Keywords: edge imbalance · graphic sequences

Discussion

Consider simple undirected graph $ G $ and let $ e=uv\in E(G) $ . The 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.

Bibliography