Show simple item record

dc.contributor.authorRies, Bernard*
dc.contributor.authorAsinowski, Andrei*
dc.date.accessioned2012-02-15T13:47:09Z
dc.date.available2012-02-15T13:47:09Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/8169
dc.language.isoenen
dc.subjectErdős–Hajnal propertyen
dc.subjectNeighborhooden
dc.subjectChordal graphsen
dc.subjectPaths on a griden
dc.subjectIntersection graphsen
dc.subject.ddc511en
dc.titleSome properties of edge intersection graphs of single-bend paths on a griden
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherDepartment of Mathematics, Technion—Israel Institute of Technology;Israël
dc.contributor.editoruniversityotherCaesarea Rothschild Institute, University of Haifa;Israël
dc.description.abstractenIn this paper we consider graphs G whose vertices can be represented as single-bend paths (i.e., paths with at most one turn) on a rectangular grid, such that two vertices are adjacent in G if and only if the corresponding paths share at least one edge of the grid. These graphs, called B1-EPG graphs, were first introduced in Golumbic et al. (2009) [13]. Here we show that the neighborhood of every vertex in a B1-EPG graph induces a weakly chordal graph. From this we conclude that the family F of B1-EPG graphs satisfies the Erdős–Hajnal property with View the MathML source, i.e., that every B1-EPG graph on n vertices contains either a clique or a stable set of size at least View the MathML source. Finally we give a characterization of B1-EPG graphs among some subclasses of chordal graphs, namely chordal bull-free graphs, chordal claw-free graphs, chordal diamond-free graphs, and special cases of split graphs.en
dc.relation.isversionofjnlnameDiscrete Mathematics
dc.relation.isversionofjnlvol312en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2012
dc.relation.isversionofjnlpages427-440en
dc.relation.isversionofdoi10.1016/j.disc.2011.10.005en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.person.labIds989*
hal.person.labIds87696*
hal.identifierhal-01509667*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record