Relaxing Meyniel graphs: condition for strongly perfect instead of very strongly perfect

Question

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.

Answer 1

You ask:

Does this mean every induced subgraph of G which are cycles of odd length at least 5 has at least 2 chords?

No, that doesn't make sense. If an induced subgraph is an induced cycle, then it contains no chords. The defining property of Meyniel graphs does not make any reference to induced subgraphs. Every odd cycle size 5 and larger contains two chords. This is a way of defining a class of graphs without an induced add cycles, since the definition prescribes how the cycles are broken (with 2 chords).

The house graph (i.e. the complement of $P_5$) is not Meyniel since the 5 vertices form a cycle but there is only one chord.

You mention that Meyniel graphs were shown to be strongly perfect and then that they were shown to be very strongly perfect. You seem to have missed the fact that Meyniel graphs were actually shown to be equivalent to the class of very strongly perfect graphs. This is important, as you later claim that the house graph (co-$P_5$) is very strongly perfect, but that graph is not Meyniel. The vertex at the top of the house is the example vertex which is not in an independent set which hits every maximal clique. Since with that top vertex, you form a maximum independent set with one of the vertices at the bottom of the house, and then the side of the house opposite your chosen bottom vertex is a maximal clique which is not hit by the independent set.

As for your conjecture, relaxing Meyniel graphs in a way that allow for 5-cycles with a single chord, I am not aware of this relaxation being studied, but I suspect it has. Meyniel graphs are also called (5,2)-odd chordal graphs, meaning every odd cycle of size 5 or more has 2 chords. In this notation, your conjecture states:

(Conjecture:) a $C_5$-free (7,2)-odd chordal graph is strongly perfect.

GraphClasses.org mentions a number of minimal superclasses of Meyniel graphs:

• $(C_5,$house)-free
• (antihole, odd hole)-free = no induced $C_5, \overline{C}_6, \overline{C}_7, C_7, \overline{C}_8, \overline{C}_9, C_9$... $\subseteq$ Perfect
• bip* graphs $\subseteq$ Perfect
• strongly even-signable = building-free and even-signable
• locally perfect graphs $\subseteq$ Perfect
• slim graphs = probe Meyniel graphs $\subseteq$ Perfect
• quasi-Meyniel $\subseteq$ Perfect
• strongly perfect $\subseteq$ Perfect

So there are (at least) 5 classes (and their equivalents) which are a superclass of Meyniel (i.e. a Meyniel relaxation) which are still perfect graphs and their relationship to strongly perfect graphs is non-comparable (meaning the class is not known to be a subclass or superclass of strongly perfect graphs). I do not know where your Meyniel relaxation lies among these.

Here is an example of one of your graphs... A 7-cycle with two chords and no induced $C_5$ (i.e. any 5-cycle contains a chord):

This graph is strongly perfect as the independent set {2,5,6} seems to hit every maximal clique. However, I believe the following graph is a counterexample to your conjecture:

Please verify that this satisfies your understanding of 'contains' and that this has the property that every odd cycle size 7 or larger has 2 chords and every 5-cycle has at least one chord. Then note that it is not strongly perfect.