3
$\begingroup$

Let $G$ is a finite simple undirected graph. Suppose there exist subgraph $G_1,G_2,\dots,G_n$ of $G$, such that $G_i \cong K_5$ or $K_{3,3}$, $E(G_i)\cap E(G_j) = \emptyset$ and $|V(G_i)\cap V(G_j)| \leq 3$, for $i\neq j$. Then, is it true that genus of $G$ is greater than or equal to $n$?

Thanks in advance.

$\endgroup$
0

1 Answer 1

4
$\begingroup$

Second try. I believe $K_{6,3}$ is a counterexample.

It is genus $1$ and contains $2$ edge disjoint $K_{3,3}$s sharing only $3$ vertices.

Explicitly:

K_{6,3}=[(0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8), (3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)]
first K_{3,3}=[(3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)]
second K_{3,3}=[(0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8)]
shared vertices 8,6,7

Added $K_{3,3n}$ are counterexamples too.

$g(K_{3,3n})=\lceil (3n-2)/4 \rceil < (3n-2) / 4 + 1$

$K_{3,3n}$ has $n$ disjoint $K_{3,3}$ sharing only $3$ vertices: connect the $3$ partition to $3$ distinct vertices from the $3n$ partition.

$\endgroup$
3
  • $\begingroup$ Suppose $K_{11}$ has 6 subgraph $G_i,1 \leq i \leq 6$, such that $G_i \cong K_5$ and $E(G_i)\cap E(G_j) = \emptyset, i\neq j$. Then $55 = |E(G)| \geq \underset{i=1}{\overset{6}\sum} |E(G_i)| =60$, which is not possible. So i think your counter example does't work, or may be i miss the point. $\endgroup$
    – bor
    Feb 10, 2014 at 7:44
  • $\begingroup$ @bor The K_11 example might indeed be wrong, let me try to fix it if possible at all... $\endgroup$
    – joro
    Feb 10, 2014 at 7:52
  • $\begingroup$ @bor I suggest K_{6,3} as counterexample, genus 1, explicit subgraphs. $\endgroup$
    – joro
    Feb 10, 2014 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.