Skip to main content
1 of 3

Relaxing Meyniel Graphs: Condition for Strongly Perfect Instead of Very Strongly Perfect

A Meyniel graph, $\mathcal{G}$ is a graph in which every cycle of odd length at least 5 has at least 2 chords.

First off, I have a technical question which is very important to me. What is meant by every cycle of odd length at least 5 has at least 2 chords?

Does this mean every induced subgraph of $\mathcal{G}$ which are cycles of odd length at least 5 has at least 2 chords? Or does this mean every cycle of odd length at least 5 "contained in $\mathcal{G}"$ has at least 2 chords? Where contained refers to a logical sense of containment in $\mathcal{G}$ (I refrain from using "subgraph" here because this is not necessarily what I mean).

For example, suppose a graph $\mathcal{L}$ has the house X graph as a subgraph (say the other subgraphs are not relevant to the discussion). See:https://mathworld.wolfram.com/HouseGraph.html

Then clearly, $\mathcal{L}$ has $C_{5}$ (chordless cycle of length $5$) also as a subgraph. However, I say here by my definition of containment, which I'm trying to define but it's very hard for me to make precise, that all odd cycles of length at least $5$ contained in $\mathcal{L}$ have 3 chords.

Here is my attempt to make the essence or significance of my definition more precise: ** take all subgraphs which are cycle graphs of odd length.

Case 1: If I can add edges from the original graph to that subgraph, without changing whether that subgraph is an odd cycle graph of length at least 5, then alter the graph by adding such edges. The number of chords of that cycle graph is then the number of chords of this "altered graph". This altered graph (not the original graph) is what is considered as "contained" in $\mathcal{G}$ then.

Case 2: If I cannot add edges from the original graph to that subgraph, without changing whether that subgraph is an odd cycle graph of length at least 5, then doing nothing (do not alter the graph). Then in this case the number of the chords of that cycle graph is the number chords of just the number of chords of that cycle graph with no alteration. That cycle graph is considered as "contained" in $\mathcal{G}$**

Take another example, Graph From Berge Paper

https://www.researchgate.net/publication/267671221_Strongly_perfect_graphs page 6.

By my definition of containment, in this graph all cycles of length $5$ contained in the graph have $0$ chords. However, it is clear that an induced cycle graph of length $5$ will have $1$ chord. Berge and Duchet say this graph is perfect but not strongly perfect (if an induced cycle graph of length $5$ with no chords existed, then the graph would not even be perfect by the strong perfect graph theorem).

This brings us to my main question:

It was proved by Ravindra that a Meyniel graph, a graph in which every odd cycle of length five or more has at least two chords, is strongly perfect. A strongly perfect graph is a graph in which every induced subgraph $H$ has an independent/stable set meeting all maximal cliques of $H$. Note such a stable set is called a strong stable set.

It was later proved that Meyniel graphs are very strongly perfect graphs, an even stronger condition, which means that every vertex of an induced subgraph, $H$, belongs to an independent set of $H$ meeting all maximal cliques of $H$.

Now, coming to the main point. Here is my conjecture:

Conjecture: A graph $\mathcal{G}$, where every cycle of length of $5$ contained in $\mathcal{G}$ has at least $1$ chord and every cycle of odd length $\geq 7$ contained in $\mathcal{G}$ has at least $2$ chords, is strongly perfect. Here, containment of odd cycles and number of chords of odd cycles means what I attempted to define in bold above.

Some motivation for this is notice that the house graph (house graph not house X graph): https://mathworld.wolfram.com/HouseGraph.html is strongly perfect. I can find a strong stable set in every possible induced subgraph (I verified for all 31 possible induced subgraphs).

Thus my point is that if I relax it that every cycle of length of $5$ contained in $\mathcal{G}$ has at least $1$ chord, then is the graph strongly perfect?

Is there any known results on this, or any research papers you could point me to? Do you think the conjecture is true or do you think there exists a counterexample. I am sorry for my lack of familiarity with unified graph theory terminology. This concept of containment always confuses me and I want to be as technical as possible as this result is very important to me. I have highlighted in bold my main points. Thanks.