Talk:Distance-hereditary graph

"It has been known for some time that the distance-hereditary graphs constitute an intersection class of graphs,[3] "

Latest comment: 3 years ago2 comments2 people in discussion

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

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

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.