File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: The circumference of a graph with no K3, t-minor

TitleThe circumference of a graph with no K3, t-minor
Authors
Chen, GSheppardson, LYu, XZang, W
KeywordsCircumference
Connectivity
Cycle
Minor
Path
Issue Date2006
PublisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jctb
Citation
Journal Of Combinatorial Theory. Series B, 2006, v. 96 n. 6, p. 822-845 How to Cite?
DOI: http://dx.doi.org/10.1016/j.jctb.2006.02.006
AbstractIt was shown by Chen and Yu that every 3-connected planar graph G contains a cycle of length at least | G |log 3 2, where | G | denotes the number of vertices of G. Thomas made a conjecture in a more general setting: there exists a function β (t) > 0 for t ≥ 3, such that every 3-connected graph G with no K3, t-minor, t ≥ 3, contains a cycle of length at least | G |β (t). We prove that this conjecture is true with β (t) = log8 t t + 1 2. We also show that every 2-connected graph with no K2, t-minor, t ≥ 3, contains a cycle of length at least | G | / tt - 1. © 2006 Elsevier Inc. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/156176
ISSN
0095-8956
2023 Impact Factor: 1.2
2023 SCImago Journal Rankings: 1.793
ISI Accession Number ID
WOS:000242914100002
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChen, Gen_US
dc.contributor.authorSheppardson, Len_US
dc.contributor.authorYu, Xen_US
dc.contributor.authorZang, Wen_US
dc.date.accessioned2012-08-08T08:40:43Z-
dc.date.available2012-08-08T08:40:43Z-
dc.date.issued2006en_US
dc.identifier.citationJournal Of Combinatorial Theory. Series B, 2006, v. 96 n. 6, p. 822-845en_US
dc.identifier.issn0095-8956en_US
dc.identifier.urihttp://hdl.handle.net/10722/156176-
dc.description.abstractIt was shown by Chen and Yu that every 3-connected planar graph G contains a cycle of length at least | G |log 3 2, where | G | denotes the number of vertices of G. Thomas made a conjecture in a more general setting: there exists a function β (t) > 0 for t ≥ 3, such that every 3-connected graph G with no K3, t-minor, t ≥ 3, contains a cycle of length at least | G |β (t). We prove that this conjecture is true with β (t) = log8 t t + 1 2. We also show that every 2-connected graph with no K2, t-minor, t ≥ 3, contains a cycle of length at least | G | / tt - 1. © 2006 Elsevier Inc. All rights reserved.en_US
dc.languageengen_US
dc.publisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jctben_US
dc.relation.ispartofJournal of Combinatorial Theory. Series Ben_US
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.subjectCircumferenceen_US
dc.subjectConnectivityen_US
dc.subjectCycleen_US
dc.subjectMinoren_US
dc.subjectPathen_US
dc.titleThe circumference of a graph with no K3, t-minoren_US
dc.typeArticleen_US
dc.identifier.emailZang, W:wzang@maths.hku.hken_US
dc.identifier.authorityZang, W=rp00839en_US
dc.description.naturepreprinten_US
dc.identifier.doi10.1016/j.jctb.2006.02.006en_US
dc.identifier.scopuseid_2-s2.0-33845342231en_US
dc.identifier.hkuros125299-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33845342231&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume96en_US
dc.identifier.issue6en_US
dc.identifier.spage822en_US
dc.identifier.epage845en_US
dc.identifier.isiWOS:000242914100002-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridChen, G=7406541233en_US
dc.identifier.scopusauthoridSheppardson, L=15127984600en_US
dc.identifier.scopusauthoridYu, X=7404115058en_US
dc.identifier.scopusauthoridZang, W=7005740804en_US
dc.identifier.issnl0095-8956-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats