Please use this identifier to cite or link to this item:
https://research.matf.bg.ac.rs/handle/123456789/216
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Aboulker, Pierre | 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 | 2012-12-31 | - |
dc.identifier.issn | 08954801 | en |
dc.identifier.uri | https://research.matf.bg.ac.rs/handle/123456789/216 | - |
dc.description.abstract | We recall several known results about minimally 2-connected graphs and show that they all follow from a decomposition theorem. Starting from an analogy with critically 2-connected graphs, we give structural characterizations of the classes of graphs that do not contain as a subgraph and as an induced subgraph, a cycle with a node that has at least two neighbors on the cycle. From these characterizations we get polynomial time recognition algorithms for these classes and polynomial time algorithms for vertex-coloring and edge-coloring. Copyright © by SIAM. | en |
dc.relation.ispartof | SIAM Journal on Discrete Mathematics | en |
dc.subject | Connectivity | en |
dc.subject | Induced subgraph | en |
dc.subject | Propeller | en |
dc.subject | Wheels | en |
dc.title | Graphs that do not contain a cycle with a node that has at least two neighbors on it | en_US |
dc.type | Article | en_US |
dc.identifier.doi | 10.1137/11084933X | - |
dc.identifier.scopus | 2-s2.0-84871562708 | - |
dc.identifier.url | https://api.elsevier.com/content/abstract/scopus_id/84871562708 | - |
dc.contributor.affiliation | Algebra and Mathematical Logic | en_US |
dc.relation.firstpage | 1510 | en |
dc.relation.lastpage | 1531 | en |
dc.relation.volume | 26 | en |
dc.relation.issue | 4 | 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
13
checked on Dec 21, 2024
Page view(s)
11
checked on Dec 24, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.