3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 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
    Commented Feb 1, 2017 at 12:52
  • $\begingroup$ I don't understand where you get your numbers from. Starting from 4 vertices, there are 1, 1, 2, 5, 14, 50, 233, 1249, 7595, 49566, 339722 planar cubic graphs as per OEIS oeis.org/A000109. How do you get 1.4 million? $\endgroup$
    – Gordon Royle
    Commented Jan 3 at 3:51

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .