2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Regarding maximal planar graphs of minimum degree 5, they can all be made using three operations starting at the icosahedron. See below Fig 7 at users.cecs.anu.edu.au/~bdm/papers/plantri-full.pdf . Now try to prove that if there is an odd hole before an operation, there is one afterwards too. I didn't attempt it. $\endgroup$
    – Brendan McKay
    Commented Jul 21 at 2:42

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .