Skip to main content
Commonmark migration
Source Link

Yuichiro Fujiwara's comments seem to answer the question in full so I am making it an answer. I quote below from Kronecker products and local joins of graphs by M. Farzan and D. A. Waller, Can. J. Math. 29 (1977), 255–269.

By a 1-contraction of $G$ we mean the removal from $G$ of each vertex of degree 1 (and its incident edge).

 

5.3 THEOREM. Let $G_1$ and $G_2$ be connected graphs with more than four vertices. Then $G_1\times G_2$ is planar if and only if either

 

(i) one of the graphs is a path and the other one is 1-contractible to a path or a circuit, or

 

(ii) one of them is a circuit and the other is 1-contractible to a path.

This leaves open only the case in which at least one of the graphs has fewer than five vertices. Proposition 5.4, which I won't bother reproducing here, covers some of these cases. Beaudou et al. addresses the case $G=K_2$. A complete solution appears to be still an open problem.

Yuichiro Fujiwara's comments seem to answer the question in full so I am making it an answer. I quote below from Kronecker products and local joins of graphs by M. Farzan and D. A. Waller, Can. J. Math. 29 (1977), 255–269.

By a 1-contraction of $G$ we mean the removal from $G$ of each vertex of degree 1 (and its incident edge).

 

5.3 THEOREM. Let $G_1$ and $G_2$ be connected graphs with more than four vertices. Then $G_1\times G_2$ is planar if and only if either

 

(i) one of the graphs is a path and the other one is 1-contractible to a path or a circuit, or

 

(ii) one of them is a circuit and the other is 1-contractible to a path.

This leaves open only the case in which at least one of the graphs has fewer than five vertices. Proposition 5.4, which I won't bother reproducing here, covers some of these cases. Beaudou et al. addresses the case $G=K_2$. A complete solution appears to be still an open problem.

Yuichiro Fujiwara's comments seem to answer the question in full so I am making it an answer. I quote below from Kronecker products and local joins of graphs by M. Farzan and D. A. Waller, Can. J. Math. 29 (1977), 255–269.

By a 1-contraction of $G$ we mean the removal from $G$ of each vertex of degree 1 (and its incident edge).

5.3 THEOREM. Let $G_1$ and $G_2$ be connected graphs with more than four vertices. Then $G_1\times G_2$ is planar if and only if either

(i) one of the graphs is a path and the other one is 1-contractible to a path or a circuit, or

(ii) one of them is a circuit and the other is 1-contractible to a path.

This leaves open only the case in which at least one of the graphs has fewer than five vertices. Proposition 5.4, which I won't bother reproducing here, covers some of these cases. Beaudou et al. addresses the case $G=K_2$. A complete solution appears to be still an open problem.

Added reference
Source Link
Timothy Chow
  • 82.6k
  • 26
  • 363
  • 587

Yuichiro Fujiwara's comment seemscomments seem to answer the question in full so I am making it an answer. I quote below from Kronecker products and local joins of graphs by M. Farzan and D. A. Waller, Can. J. Math. 29 (1977), 255–269.

By a 1-contraction of $G$ we mean the removal from $G$ of each vertex of degree 1 (and its incident edge).

5.3 THEOREM. Let $G_1$ and $G_2$ be connected graphs with more than four vertices. Then $G_1\times G_2$ is planar if and only if either

(i) one of the graphs is a path and the other one is 1-contractible to a path or a circuit, or

(ii) one of them is a circuit and the other is 1-contractible to a path.

Proposition 5.4, which I won't bother reproducing here, handlesThis leaves open only the case wherein which at least one of the graphs has fewer than five vertices. Proposition 5.4, which I won't bother reproducing here, covers some of these cases. Beaudou et al. addresses the case $G=K_2$. A complete solution appears to be still an open problem.

Yuichiro Fujiwara's comment seems to answer the question in full so I am making it an answer. I quote below from Kronecker products and local joins of graphs by M. Farzan and D. A. Waller, Can. J. Math. 29 (1977), 255–269.

By a 1-contraction of $G$ we mean the removal from $G$ of each vertex of degree 1 (and its incident edge).

5.3 THEOREM. Let $G_1$ and $G_2$ be connected graphs with more than four vertices. Then $G_1\times G_2$ is planar if and only if either

(i) one of the graphs is a path and the other one is 1-contractible to a path or a circuit, or

(ii) one of them is a circuit and the other is 1-contractible to a path.

Proposition 5.4, which I won't bother reproducing here, handles the case where at least one of the graphs has fewer than five vertices.

Yuichiro Fujiwara's comments seem to answer the question in full so I am making it an answer. I quote below from Kronecker products and local joins of graphs by M. Farzan and D. A. Waller, Can. J. Math. 29 (1977), 255–269.

By a 1-contraction of $G$ we mean the removal from $G$ of each vertex of degree 1 (and its incident edge).

5.3 THEOREM. Let $G_1$ and $G_2$ be connected graphs with more than four vertices. Then $G_1\times G_2$ is planar if and only if either

(i) one of the graphs is a path and the other one is 1-contractible to a path or a circuit, or

(ii) one of them is a circuit and the other is 1-contractible to a path.

This leaves open only the case in which at least one of the graphs has fewer than five vertices. Proposition 5.4, which I won't bother reproducing here, covers some of these cases. Beaudou et al. addresses the case $G=K_2$. A complete solution appears to be still an open problem.

Source Link
Timothy Chow
  • 82.6k
  • 26
  • 363
  • 587

Yuichiro Fujiwara's comment seems to answer the question in full so I am making it an answer. I quote below from Kronecker products and local joins of graphs by M. Farzan and D. A. Waller, Can. J. Math. 29 (1977), 255–269.

By a 1-contraction of $G$ we mean the removal from $G$ of each vertex of degree 1 (and its incident edge).

5.3 THEOREM. Let $G_1$ and $G_2$ be connected graphs with more than four vertices. Then $G_1\times G_2$ is planar if and only if either

(i) one of the graphs is a path and the other one is 1-contractible to a path or a circuit, or

(ii) one of them is a circuit and the other is 1-contractible to a path.

Proposition 5.4, which I won't bother reproducing here, handles the case where at least one of the graphs has fewer than five vertices.

Post Made Community Wiki by Timothy Chow