Please use this identifier to cite or link to this item:
https://research.matf.bg.ac.rs/handle/123456789/216
Title: | Graphs that do not contain a cycle with a node that has at least two neighbors on it | Authors: | Aboulker, Pierre Radovanović, Marko Trotignon, Nicolas Vušković, Kristina |
Affiliations: | Algebra and Mathematical Logic | Keywords: | Connectivity;Induced subgraph;Propeller;Wheels | Issue Date: | 31-Dec-2012 | Journal: | SIAM Journal on Discrete Mathematics | 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. |
URI: | https://research.matf.bg.ac.rs/handle/123456789/216 | ISSN: | 08954801 | DOI: | 10.1137/11084933X |
Appears in Collections: | Research outputs |
Show full item record
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.