Show simple item record

dc.contributor.authorRies, Bernard*
dc.contributor.authorGolumbic, Martin Charles*
dc.contributor.authorCohen, Elad*
dc.date.accessioned2014-09-22T11:51:51Z
dc.date.available2014-09-22T11:51:51Z
dc.date.issued2014
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/13958
dc.language.isoenen
dc.subjectInduced subgraphen
dc.subjectIntersection graphen
dc.subjectGriden
dc.subjectCotreeen
dc.subjectCographen
dc.subject.ddc511en
dc.titleCharacterizations of cographs as intersection graphs of paths on a griden
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherCaesarea Rothschild Institute and Department of Computer Science, University of Haifa, Mount Carmel, Haifa;Israël
dc.description.abstractenA cograph is a graph which does not contain any induced path on four vertices. In this paper, we characterize those cographs that are intersection graphs of paths on a grid in the following two cases: (i) the paths on the grid all have at most one bend and the intersections concern edges (→B1→B1-EPG); (ii) the paths on the grid are not bended and the intersections concern vertices (→B0→B0-VPG). In both cases, we give a characterization by a family of forbidden induced subgraphs. We further present linear-time algorithms to recognize B1B1-EPG cographs and B0B0-VPG cographs using their cotree.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol178en
dc.relation.isversionofjnldate2014
dc.relation.isversionofjnlpages46-57en
dc.relation.isversionofdoi10.1016/j.dam.2014.06.020en
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.forthcomingnonen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.person.labIds989*
hal.person.labIds87696*
hal.person.labIds87696*
hal.identifierhal-01509552*


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