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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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
    Commented Feb 10, 2014 at 7:52
  • $\begingroup$ @bor I suggest K_{6,3} as counterexample, genus 1, explicit subgraphs. $\endgroup$
    – joro
    Commented Feb 10, 2014 at 9:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .