BROWSE

Related Scientist

's photo.

수리및계산과학연구단
more info

ITEM VIEW & DOWNLOAD

Matching theory and Barnette's conjecture

DC Field Value Language
dc.contributor.authorGorsky, Maximilian-
dc.contributor.authorSteiner, Raphael-
dc.contributor.authorSebastian Wiederrecht-
dc.date.accessioned2023-04-10T22:01:01Z-
dc.date.available2023-04-10T22:01:01Z-
dc.date.created2022-12-06-
dc.date.issued2023-02-
dc.identifier.issn0012-365X-
dc.identifier.urihttps://pr.ibs.re.kr/handle/8788114/13232-
dc.description.abstract© 2022 Elsevier B.V.Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian. A graph, other than the path of length three, is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity. As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. (1985) [14]. These allow us to check whether a graph we generated is a brace.-
dc.language영어-
dc.publisherElsevier BV-
dc.titleMatching theory and Barnette's conjecture-
dc.typeArticle-
dc.type.rimsART-
dc.identifier.wosid000885354400001-
dc.identifier.scopusid2-s2.0-85141531050-
dc.identifier.rimsid79398-
dc.contributor.affiliatedAuthorSebastian Wiederrecht-
dc.identifier.doi10.1016/j.disc.2022.113249-
dc.identifier.bibliographicCitationDiscrete Mathematics, v.346, no.2-
dc.relation.isPartOfDiscrete Mathematics-
dc.citation.titleDiscrete Mathematics-
dc.citation.volume346-
dc.citation.number2-
dc.type.docTypeArticle-
dc.description.journalClass1-
dc.description.journalClass1-
dc.description.isOpenAccessN-
dc.description.journalRegisteredClassscie-
dc.description.journalRegisteredClassscopus-
dc.relation.journalResearchAreaMathematics-
dc.relation.journalWebOfScienceCategoryMathematics-
dc.subject.keywordPlusPFAFFIAN ORIENTATIONS-
dc.subject.keywordPlusPERMANENTS-
dc.subject.keywordPlusGRAPHS-
dc.subject.keywordPlusCYCLES-
dc.subject.keywordAuthorBarnette&apos-
dc.subject.keywordAuthors conjecture-
dc.subject.keywordAuthorBipartite graphs-
dc.subject.keywordAuthorCubic graphs-
dc.subject.keywordAuthorMatching theory-
dc.subject.keywordAuthorPerfect matching-
dc.subject.keywordAuthorPfaffian graphs-
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

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

Browse