Skip to main content
1 of 2
JimN
  • 265
  • 1
  • 13

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):

enter image description here

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:

enter image description here

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.

JimN
  • 265
  • 1
  • 13