2
$\begingroup$

A graph $G$ is said to be perfect if $\chi(H)=\omega(H)$ hold for any induced subgraph $H_i\subseteq G$ (and so for $G$ itself, too)

For maximal planar graphs with connectivity 3, it is easy to construct a class of perfect graphs, such as planar 3-trees. For the connectivity 4, we can also construct infinitely many examples, like graphs in the previous link Are there examples of non-perfect graphs among these graphs (Thanks to Misha Lavrov). However, for the connectivity 5, I have not yet found a corresponding example. Could it be that any 5-connected (maximal) planar graph is not perfect?

The following is SageMath code (Sage 10.3) for searching. I haven't seen it yet:

# Generate 5-connected maximal planar graphs using the Plantri generator
# Note: The value 12 can be adjusted to a higher number for generating larger graphs 
gen = graphs.plantri_gen("12 -c5 ")

# Use a generator expression to find the first perfect graph

p = next((g for g in gen if g.is_perfect()), None)
if p is not None:
    print(p)
else:
    print("No graphs found")
$\endgroup$
4
  • $\begingroup$ I seem to have found evidence because it always contains a 5-hole (the structure around a vertex of degree 5; 5-connectivity ensures that the neighborhood of this vertex induces a cycle of length 5). $\endgroup$
    – licheng
    Commented Jun 8 at 12:07
  • $\begingroup$ I don't see how 5-connectivity ensures that the neighborhood of this vertex induces a cycle of length 5, can you elaborate more on that? I can show that such a graph is not chordal, so there will be an induced cycle of length $4$. $\endgroup$
    – koifish
    Commented Jun 9 at 12:11
  • $\begingroup$ I will add a solution right away. If you prove it contains an induced 4-cycle, you can provide an answer. Thank you. $\endgroup$
    – licheng
    Commented Jun 9 at 12:24
  • $\begingroup$ I think I just proved a small property of the graph -- not very sure how it solves anything. It cannot be a chordal graph because chordal graphs are recursively constructed via clique sums of complete graphs. If $G$ is $5$-connected, the summands must be $K_t$ for $t \geq 6$ -- but then $G$ cannot be planar. $\endgroup$
    – koifish
    Commented Jun 9 at 12:31

1 Answer 1

Reset to default
2
$\begingroup$

Let $G$ be a 5-connected maximal planar graph. It is easy to prove that the minimum degree of $G$ is 5. Let $v$ be a vertex of degree $5$ and $N_G(v)=\{1,2,3,4,5\}$. Then, based on maximality, the local drawing of $N[v]$ is as follows:

enter image description here

Then $123451$ is a 5-cycle. Moreover, this 5-cycle cannot have a chord $xy$ where $1\le x<y \le 5$; otherwise, $xvyx$ would form a separating 3-cycle of $G$.

(For example, $x=1, y=4$, then there are vertices both inside (vertex $5$) and outside (vertex $2$) the cycle $1v4$. Vertices $1, 4, v$ form a 3-separator.)

This contradicts the 5-connectivity.

enter image description here

So $G$ is not perfect.

$\endgroup$
6
  • $\begingroup$ Why should $xvyx$ separate $G$? $\endgroup$
    – koifish
    Commented Jun 9 at 12:47
  • $\begingroup$ @koifish I added some explanations. $\endgroup$
    – licheng
    Commented Jun 9 at 12:58
  • $\begingroup$ Right, I think that works! $\endgroup$
    – koifish
    Commented Jun 9 at 13:01
  • $\begingroup$ Nice proof, looks good! $\endgroup$
    – Brandon du Preez
    Commented Jun 17 at 16:48
  • $\begingroup$ @Brandon du Preez The proof cannot be extended to any planar graphs with connectivity 5 or minimum degree 5. I even believe that any planar perfect graphs has minimum degree 4. I plan to ask a new question. $\endgroup$
    – licheng
    Commented Jun 18 at 2:05

You must log in to answer this question.

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