Skip to main content
MathOverflow

Return to Question

deleted 5 characters in body
Source Link
Licheng Zhang
Licheng Zhang
  • 1.9k
  • 6
  • 17

I asked this question on math stack, but didn't get any response, so I'm askingI ask it here.

In a previous post, I proved that no 5-connected maximal planar graph is perfect. (A perfect graph is a graph $G$ such that for every induced subgraph of $G$, the clique number equals the chromatic number）

Naturally, I wanted to ask whether there exists a 5-connected planar graph that is perfect. In some computer searches, I couldn't even find a planar perfect graph with minimum degree 5. I have no sufficient reason to show the non-existence, but I also can't think of a construction.

I asked this question on math stack, but didn't get any response, so I'm asking it here.

In a previous post, I proved that no 5-connected maximal planar graph is perfect. (A perfect graph is a graph $G$ such that for every induced subgraph of $G$, the clique number equals the chromatic number）

Naturally, I wanted to ask whether there exists a 5-connected planar graph that is perfect. In some computer searches, I couldn't even find a planar perfect graph with minimum degree 5. I have no sufficient reason to show the non-existence, but I also can't think of a construction.

I asked this question on math stack, but didn't get any response, so I ask it here.

In a previous post, I proved that no 5-connected maximal planar graph is perfect. (A perfect graph is a graph $G$ such that for every induced subgraph of $G$, the clique number equals the chromatic number）

Naturally, I wanted to ask whether there exists a 5-connected planar graph that is perfect. In some computer searches, I couldn't even find a planar perfect graph with minimum degree 5. I have no sufficient reason to show the non-existence, but I also can't think of a construction.

Source Link
Licheng Zhang
Licheng Zhang
  • 1.9k
  • 6
  • 17

Does there exist a 5-connected planar graph that is perfect?

I asked this question on math stack, but didn't get any response, so I'm asking it here.

In a previous post, I proved that no 5-connected maximal planar graph is perfect. (A perfect graph is a graph $G$ such that for every induced subgraph of $G$, the clique number equals the chromatic number）

Naturally, I wanted to ask whether there exists a 5-connected planar graph that is perfect. In some computer searches, I couldn't even find a planar perfect graph with minimum degree 5. I have no sufficient reason to show the non-existence, but I also can't think of a construction.