1. Research with MATF
  2. MATF
  3. Research outputs
Please use this identifier to cite or link to this item: https://research.matf.bg.ac.rs/handle/123456789/216
DC FieldValueLanguage
dc.contributor.authorAboulker, Pierreen_US
dc.contributor.authorRadovanović, Markoen_US
dc.contributor.authorTrotignon, Nicolasen_US
dc.contributor.authorVušković, Kristinaen_US
dc.date.accessioned2022-08-06T17:23:28Z-
dc.date.available2022-08-06T17:23:28Z-
dc.date.issued2012-12-31-
dc.identifier.issn08954801en
dc.identifier.urihttps://research.matf.bg.ac.rs/handle/123456789/216-
dc.description.abstractWe 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_US
dc.language.isoenen_US
dc.publisherSIAM Society of Industrial and Applied Mathematicsen_US
dc.relation.ispartofSIAM Journal on Discrete Mathematicsen_US
dc.subjectConnectivityen_US
dc.subjectInduced subgraphen_US
dc.subjectPropelleren_US
dc.subjectWheelsen_US
dc.titleGraphs that do not contain a cycle with a node that has at least two neighbors on iten_US
dc.typeArticleen_US
dc.identifier.doi10.1137/11084933X-
dc.identifier.scopus2-s2.0-84871562708-
dc.identifier.isi000312700400002-
dc.identifier.urlhttps://api.elsevier.com/content/abstract/scopus_id/84871562708-
dc.contributor.affiliationAlgebra and Mathematical Logicen_US
dc.relation.issn0895-4801en_US
dc.description.rankM22en_US
dc.relation.firstpage1510en_US
dc.relation.lastpage1531en_US
dc.relation.volume26en_US
dc.relation.issue4en_US
item.openairetypeArticle-
item.fulltextNo Fulltext-
item.languageiso639-1en-
item.cerifentitytypePublications-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.grantfulltextnone-
crisitem.author.deptAlgebra and Mathematical Logic-
crisitem.author.orcid0000-0002-6990-1793-
Appears in Collections:Research outputs
Show simple item record

SCOPUSTM   
Citations

13
checked on Nov 5, 2025

Page view(s)

11
checked on Jan 19, 2025

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.