Skip to main content
added 24 characters in body
Source Link
B.Hueber
  • 1.2k
  • 4
  • 10

I have not too much experience with graph theory, so I am basically asking if someone knows if the answer to the following question follows from some theorem of graph theory (which I'm probably unaware of):

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a finite and simple graph with the following properties:

  1. It is bipartite.
  2. It is $3$-valent and admits a proper $3$-edge colouring, i.e. we can colour all edges by $3$ colours such that the $3$ edges adjacent to some vertex have different colours.
  3. It is spherical, i.e. $\vert\mathcal{F}\vert-\vert\mathcal{E}\vert+\vert\mathcal{V}\vert=2$, where $\mathcal{F}$ is the set of "faces", i.e. the set of all the bi-coloured cycles (=maximal connected components of two colours). It is actually a well-known fact from "crystallization theory" that this is equivalent to saying that the graph can be drawn in such a way that is planar and such that all the faces of the graph (=closed paths enclosing some area) are actually also "faces" in the sense defined above, i.e. the only consist of $2$ colours.

Under these assumptions, does there exists a closed path in the graph which is maximal in the sense that it touches every vertex of $\mathcal{G}$ exactly once?

I think graphs with these properties are called Hamiltonian in the graph theory literature. If this has any relevance, note that the graph $\mathcal{G}$ is actually balanced bipartite, which follows by combining bipartitness and the fact that it admits a proper edge colouring.

EDIT: I just found on the internet that what I am trying to prove for a few days now is very similar to what is called "Barnette's conjecture". So, I guess the question might be much harder then I thought^^

I have not too much experience with graph theory, so I am basically asking if someone knows if the answer to the following question follows from some theorem of graph theory (which I'm probably unaware of):

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a finite and simple graph with the following properties:

  1. It is bipartite.
  2. It is $3$-valent and admits a proper $3$-edge colouring, i.e. we can colour all edges by $3$ colours such that the $3$ edges adjacent to some vertex have different colours.
  3. It is spherical, i.e. $\vert\mathcal{F}\vert-\vert\mathcal{E}\vert+\vert\mathcal{V}\vert=2$, where $\mathcal{F}$ is the set of "faces", i.e. the set of all the bi-coloured cycles (=maximal connected components of two colours). It is actually a well-known fact from "crystallization theory" that this is equivalent to saying that the graph can be drawn in such a way that all the faces of the graph (=closed paths enclosing some area) are actually also "faces" in the sense defined above, i.e. the only consist of $2$ colours.

Under these assumptions, does there exists a closed path in the graph which is maximal in the sense that it touches every vertex of $\mathcal{G}$ exactly once?

I think graphs with these properties are called Hamiltonian in the graph theory literature. If this has any relevance, note that the graph $\mathcal{G}$ is actually balanced bipartite, which follows by combining bipartitness and the fact that it admits a proper edge colouring.

EDIT: I just found on the internet that what I am trying to prove for a few days now is very similar to what is called "Barnette's conjecture". So, I guess the question might be much harder then I thought^^

I have not too much experience with graph theory, so I am basically asking if someone knows if the answer to the following question follows from some theorem of graph theory (which I'm probably unaware of):

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a finite and simple graph with the following properties:

  1. It is bipartite.
  2. It is $3$-valent and admits a proper $3$-edge colouring, i.e. we can colour all edges by $3$ colours such that the $3$ edges adjacent to some vertex have different colours.
  3. It is spherical, i.e. $\vert\mathcal{F}\vert-\vert\mathcal{E}\vert+\vert\mathcal{V}\vert=2$, where $\mathcal{F}$ is the set of "faces", i.e. the set of all the bi-coloured cycles (=maximal connected components of two colours). It is actually a well-known fact from "crystallization theory" that this is equivalent to saying that the graph can be drawn in such a way that is planar and such that all the faces of the graph (=closed paths enclosing some area) are actually also "faces" in the sense defined above, i.e. the only consist of $2$ colours.

Under these assumptions, does there exists a closed path in the graph which is maximal in the sense that it touches every vertex of $\mathcal{G}$ exactly once?

I think graphs with these properties are called Hamiltonian in the graph theory literature. If this has any relevance, note that the graph $\mathcal{G}$ is actually balanced bipartite, which follows by combining bipartitness and the fact that it admits a proper edge colouring.

EDIT: I just found on the internet that what I am trying to prove for a few days now is very similar to what is called "Barnette's conjecture". So, I guess the question might be much harder then I thought^^

added 211 characters in body
Source Link
B.Hueber
  • 1.2k
  • 4
  • 10

I have not too much experience with graph theory, so I am basically asking if someone knows if the answer to the following question follows from some theorem of graph theory (which I'm probably unaware of):

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a finite and simple graph with the following properties:

  1. It is bipartite.
  2. It is $3$-valent and admits a proper $3$-edge colouring, i.e. we can colour all edges by $3$ colours such that the $3$ edges adjacent to some vertex have different colours.
  3. It is spherical, i.e. $\vert\mathcal{F}\vert-\vert\mathcal{E}\vert+\vert\mathcal{V}\vert=2$, where $\mathcal{F}$ is the set of "faces", i.e. the set of all the bi-coloured cycles (=maximal connected components of two colours). It is actually a well-known fact from "crystallization theory" that this is equivalent to saying that the graph can be drawn in such a way that all the faces of the graph (=closed paths enclosing some area) are actually also "faces" in the sense defined above, i.e. the only consist of $2$ colours.

Under these assumptions, does there exists a closed path in the graph which is maximal in the sense that it touches every vertex of $\mathcal{G}$ exactly once?

I think graphs with these properties are called Hamiltonian in the graph theory literature. If this has any relevance, note that the graph $\mathcal{G}$ is actually balanced bipartite, which follows by combining bipartitness and the fact that it admits a proper edge colouring.

EDIT: I just found on the internet that what I am trying to prove for a few days now is very similar to what is called "Barnette's conjecture". So, I guess the question might be much harder then I thought^^

I have not too much experience with graph theory, so I am basically asking if someone knows if the answer to the following question follows from some theorem of graph theory (which I'm probably unaware of):

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a finite and simple graph with the following properties:

  1. It is bipartite.
  2. It is $3$-valent and admits a proper $3$-edge colouring, i.e. we can colour all edges by $3$ colours such that the $3$ edges adjacent to some vertex have different colours.
  3. It is spherical, i.e. $\vert\mathcal{F}\vert-\vert\mathcal{E}\vert+\vert\mathcal{V}\vert=2$, where $\mathcal{F}$ is the set of "faces", i.e. the set of all the bi-coloured cycles (=maximal connected components of two colours). It is actually a well-known fact from "crystallization theory" that this is equivalent to saying that the graph can be drawn in such a way that all the faces of the graph (=closed paths enclosing some area) are actually also "faces" in the sense defined above, i.e. the only consist of $2$ colours.

Under these assumptions, does there exists a closed path in the graph which is maximal in the sense that it touches every vertex of $\mathcal{G}$ exactly once?

I think graphs with these properties are called Hamiltonian in the graph theory literature. If this has any relevance, note that the graph $\mathcal{G}$ is actually balanced bipartite, which follows by combining bipartitness and the fact that it admits a proper edge colouring.

I have not too much experience with graph theory, so I am basically asking if someone knows if the answer to the following question follows from some theorem of graph theory (which I'm probably unaware of):

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a finite and simple graph with the following properties:

  1. It is bipartite.
  2. It is $3$-valent and admits a proper $3$-edge colouring, i.e. we can colour all edges by $3$ colours such that the $3$ edges adjacent to some vertex have different colours.
  3. It is spherical, i.e. $\vert\mathcal{F}\vert-\vert\mathcal{E}\vert+\vert\mathcal{V}\vert=2$, where $\mathcal{F}$ is the set of "faces", i.e. the set of all the bi-coloured cycles (=maximal connected components of two colours). It is actually a well-known fact from "crystallization theory" that this is equivalent to saying that the graph can be drawn in such a way that all the faces of the graph (=closed paths enclosing some area) are actually also "faces" in the sense defined above, i.e. the only consist of $2$ colours.

Under these assumptions, does there exists a closed path in the graph which is maximal in the sense that it touches every vertex of $\mathcal{G}$ exactly once?

I think graphs with these properties are called Hamiltonian in the graph theory literature. If this has any relevance, note that the graph $\mathcal{G}$ is actually balanced bipartite, which follows by combining bipartitness and the fact that it admits a proper edge colouring.

EDIT: I just found on the internet that what I am trying to prove for a few days now is very similar to what is called "Barnette's conjecture". So, I guess the question might be much harder then I thought^^

Source Link
B.Hueber
  • 1.2k
  • 4
  • 10

Are 3-valent, balanced bipartite, proper-edge coloured spherical graphs Hamiltonian?

I have not too much experience with graph theory, so I am basically asking if someone knows if the answer to the following question follows from some theorem of graph theory (which I'm probably unaware of):

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a finite and simple graph with the following properties:

  1. It is bipartite.
  2. It is $3$-valent and admits a proper $3$-edge colouring, i.e. we can colour all edges by $3$ colours such that the $3$ edges adjacent to some vertex have different colours.
  3. It is spherical, i.e. $\vert\mathcal{F}\vert-\vert\mathcal{E}\vert+\vert\mathcal{V}\vert=2$, where $\mathcal{F}$ is the set of "faces", i.e. the set of all the bi-coloured cycles (=maximal connected components of two colours). It is actually a well-known fact from "crystallization theory" that this is equivalent to saying that the graph can be drawn in such a way that all the faces of the graph (=closed paths enclosing some area) are actually also "faces" in the sense defined above, i.e. the only consist of $2$ colours.

Under these assumptions, does there exists a closed path in the graph which is maximal in the sense that it touches every vertex of $\mathcal{G}$ exactly once?

I think graphs with these properties are called Hamiltonian in the graph theory literature. If this has any relevance, note that the graph $\mathcal{G}$ is actually balanced bipartite, which follows by combining bipartitness and the fact that it admits a proper edge colouring.