Talk:Distance-hereditary graph
Add topicLatest comment: 3 years ago by David Eppstein in topic "It has been known for some time that the distance-hereditary graphs constitute an intersection class of graphs,[3] "
 | This article is rated B-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
"It has been known for some time that the distance-hereditary graphs constitute an intersection class of graphs,[3] "
[edit]What does this mean? The reference does not really help I think, I couldn't even find a mention of DH graphs there. Any simple graph can be given an intersection model (there's even a proof here https://en.wikipedia.org/wiki/Intersection_graph). I suppose it means there is some well defined family of sets that give rise to DH graphs, but it's hard for me see how that can be proven without giving the family of sets like the next part of this sentence. If we just mean that any DH graph can be given an intersection model, then sure, but we do not need the DH hypothesis. So, in a way, I don't think this is strictly false, but quite meaningless and misleading. Any opinions? Mtzguido (talk) 19:09, 20 November 2022 (UTC)
- See the last paragraph of Intersection graph § Classes of intersection graphs, and the reference doi:10.1016/0012-365X(85)90047-0 from that paragraph. It is not enough that each individual graph is an intersection graph. The whole family of graphs needs to be defined as intersection graphs in a way that can be kept consistent when you duplicate vertices or take induced subgraphs. —David Eppstein (talk) 19:52, 20 November 2022 (UTC)