6
$\begingroup$

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?

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Apr 11, 2014 at 22:27
  • 1
    $\begingroup$ @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. $\endgroup$
    – NisaiVloot
    Apr 11, 2014 at 23:04
  • 1
    $\begingroup$ @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? $\endgroup$
    – NisaiVloot
    Apr 11, 2014 at 23:10
  • 3
    $\begingroup$ 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.) $\endgroup$
    – Sasho Nikolov
    Apr 12, 2014 at 1:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – daniello
    Nov 8, 2014 at 10:56

1 Answer 1

Reset to default
1
$\begingroup$

If I would like to know something about intersection models, the first reference I would check is the "Topics in Intersection Graph Theory" by McKee and McMorris. Theorem 1.5 answers your (combinatorial) question.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Thanks; as you can expect I don't have access to this book so may I ask what is the exact result? After all this site is about the free exchange of scientific information :) $\endgroup$
    – NisaiVloot
    Apr 12, 2014 at 5:10
  • 3
    $\begingroup$ Thm 1.5 of the book states that a if graph class is a nicely-behaved hereditary class, then it is an intersection class. And it goes on to say: "While [thm 1.5] can be used to show that a particular set of graphs is an intersection class, that is a long way from actually finding a suitable [representation] and proving that it works." So I don't think this necessarily answers the question here. Theorem 1.1 also states "Every graph is an intersection graph." The interesting open question on weakly chordal graphs is whether there is a nice/geometric intersection model for them (and to find it) $\endgroup$
    – JimN
    Jun 12, 2014 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.