We say that a $2$-coloring of a graph $G$ is unfriendly if every vertex has at least as many neighbors of the color opposite to his own. Such a coloring always exist and can be obtained by partitioning the graph into two sets that maximize the number of edges between them.

Specifically for a cubic graph $G$ a unfriendly coloring is a partition $(A,B)$ of $V(G)$ so that every vertex in $A$ has at least two neighbors in $B$ and vice versa.

We say that a cubic graph is imbalanced if it has a unfriendly partition where the two parts have different sizes.

For example, $K_4$ is not imbalanced and so isn't the cube graph $Q_3$.

Out of $1413230$ cubic planar graphs on at most $24$ vertices, there are precisely $2160$ graphs that are not imbalanced and they are all Hamiltonian. Similarly all snarks on up to $32$ vertices are imbalanced.

Hence I wonder

Is every cubic non-Hamiltonian graph imbalanced?

I would like to understand the notion of imbalanced a little bit better, so any other structural remarks about such graphs are also welcome.

  • 4
    $\begingroup$ You probably need to add "planar" or "2-edge-connected" in your question, otherwise the answer is negative. Consider two copies of $K_{3,3}$, remove an edge $uv$ in the first copy, and an edge $xy$ in the second copy. Then add two vertices $w$ and $z$, joined by an edge, such that $w$ is adjacent to $u$ and $v$, and $z$ is adjacent to $x$ and $y$. It is not difficult to show that an unfriendly partition is necessarily a proper 2-coloring, and is therefore balanced. You should maybe look at this paper related to your question arxiv.org/abs/1504.03500 $\endgroup$ – Louis Esperet Feb 1 '17 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.