# Intersection models for weakly chordal graphs?

Due to the apparent unpopularity of my previous posts, I'd like to post a question about graph theory which seems to be a popular topic here :)

Among the many known classes of perfect graphs, there are three classes that I find especially interesting:

(1) the weakly chordal graphs, whose obstruction set is $\{C_n,\bar{C_n} : n \geq 5\}$,

(2) the chordal graphs, whose obstruction set is $\{C_n : n \geq 4\}$,

(3) the strongly chordal graphs, whose obstruction set is $\{C_n : n \geq 4\} \cup \{S_n : n \geq 3\}$.

Here, $C_n$ denotes the $n$-cycle, and $S_n$ denotes the $n$-sun (obtained by starting from a cycle $x_1 ... x_n$ and adding the edges $x_i y_i x_{i+1}$ for $1 \leq i \leq n$).

These classes admit polynomial algorithms for clique/independent set, the most general one being for the class of weakly chordal graphs and uses a clever 'two-pair contraction' argument (see 'Optimizing weakly triangulated graphs' by R. Hayward, C.T. Hoang and F. Maffray).

Intersection models are known for classes (2) and (3) as they correspond to the clique graphs of acyclic, resp. totally balanced, hypergraphs. Are there any known results about intersection models for weakly chordal graphs?

As a side note, there is a recursive construction of totally balanced hypergraphs due to Lehel (see 'A characterization of totally balanced matrices'), and I was also wondering about possible algorithmic applications of this result?

• Besides throwing in a couple of side remarks about algorithms, this is still a math question. I asked you this once but your answer made little sense: is there a reason you are posting your questions here, where you don't get answers and they are not popular, rather than in Math@SE or in Mathoverflow where they would fit better? It makes no sense to me? And are effectively "spamming" the site. Apr 11, 2014 at 22:27
• @SashoNikolov: I didn't read the paper, but judging from the abstract it doesn't answer my question as it only considers a proper subclass of the weakly chordal graphs. Therefore, I assume that the question is still open. Apr 11, 2014 at 23:04
• @SureshVenkat: well, from an European perspective my questions belong to theoretical computer science in a broad sense - and the more math-oriented questions still have some constructive/algorithmic aspects that make them suited to this site, I think. Then again I can understand that people from 'Theory A' are more interested in things like TOC/CC/AGT and the like, but this shouldn't be a reason for peer exclusion I presume? Apr 11, 2014 at 23:10
• I doubt the truth of your statement above. While algebra or logic may be more relevant to theory B, a non-computational question about these will not be theory B in general. Unless you do try to connect your questions to some kind of computer science, be it theory A or B or something else, I don't think they will be more popular. And I still don't understand why you would neither provide the connection, nor ask at Math@SE. (You are right about this question, they only characterize a subclass of weakly chordal graphs.) Apr 12, 2014 at 1:06
• Structural characterizations such as these are frequently discussed at conferences such as WG, COCOON and IWOCA which, at least in my opinion, are tcs conferences. Nov 8, 2014 at 10:56