Please use this identifier to cite or link to this item:
https://research.matf.bg.ac.rs/handle/123456789/220
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Diot, Emilie | en_US |
dc.contributor.author | Radovanović, Marko | en_US |
dc.contributor.author | Trotignon, Nicolas | en_US |
dc.contributor.author | Vušković, Kristina | en_US |
dc.date.accessioned | 2022-08-06T17:23:28Z | - |
dc.date.available | 2022-08-06T17:23:28Z | - |
dc.date.issued | 2020-07-01 | - |
dc.identifier.issn | 00958956 | en |
dc.identifier.uri | https://research.matf.bg.ac.rs/handle/123456789/220 | - |
dc.description.abstract | Truemper configurations are four types of graphs (namely thetas, wheels, prisms and pyramids) that play an important role in the proof of several decomposition theorems for hereditary graph classes. In this paper, we prove two structure theorems: one for graphs with no thetas, wheels and prisms as induced subgraphs, and one for graphs with no thetas, wheels and pyramids as induced subgraphs. A consequence is a polynomial time recognition algorithms for these two classes. In Part II of this series we generalize these results to graphs with no thetas and wheels as induced subgraphs, and in Parts III and IV, using the obtained structure, we solve several optimization problems for these graphs. | en |
dc.relation.ispartof | Journal of Combinatorial Theory. Series B | en |
dc.subject | 2-Join | en |
dc.subject | Clique cutset | en |
dc.subject | Decomposition | en |
dc.subject | Induced subgraph | en |
dc.subject | Recognition algorithm | en |
dc.subject | Structure theorem | en |
dc.subject | Truemper configuration | en |
dc.title | The (theta, wheel)-free graphs Part I: Only-prism and only-pyramid graphs | en_US |
dc.type | Article | en_US |
dc.identifier.doi | 10.1016/j.jctb.2017.12.004 | - |
dc.identifier.scopus | 2-s2.0-85041617293 | - |
dc.identifier.url | https://api.elsevier.com/content/abstract/scopus_id/85041617293 | - |
dc.contributor.affiliation | Algebra and Mathematical Logic | en_US |
dc.relation.firstpage | 123 | en |
dc.relation.lastpage | 147 | en |
dc.relation.volume | 143 | en |
item.fulltext | No Fulltext | - |
item.openairecristype | http://purl.org/coar/resource_type/c_18cf | - |
item.cerifentitytype | Publications | - |
item.grantfulltext | none | - |
item.openairetype | Article | - |
crisitem.author.dept | Algebra and Mathematical Logic | - |
crisitem.author.orcid | 0000-0002-6990-1793 | - |
Appears in Collections: | Research outputs |
SCOPUSTM
Citations
7
checked on Dec 21, 2024
Page view(s)
10
checked on Dec 24, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.