Matching theory and Barnette's conjecture
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Gorsky, Maximilian | - |
dc.contributor.author | Steiner, Raphael | - |
dc.contributor.author | Sebastian Wiederrecht | - |
dc.date.accessioned | 2023-04-10T22:01:01Z | - |
dc.date.available | 2023-04-10T22:01:01Z | - |
dc.date.created | 2022-12-06 | - |
dc.date.issued | 2023-02 | - |
dc.identifier.issn | 0012-365X | - |
dc.identifier.uri | https://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.publisher | Elsevier BV | - |
dc.title | Matching theory and Barnette's conjecture | - |
dc.type | Article | - |
dc.type.rims | ART | - |
dc.identifier.wosid | 000885354400001 | - |
dc.identifier.scopusid | 2-s2.0-85141531050 | - |
dc.identifier.rimsid | 79398 | - |
dc.contributor.affiliatedAuthor | Sebastian Wiederrecht | - |
dc.identifier.doi | 10.1016/j.disc.2022.113249 | - |
dc.identifier.bibliographicCitation | Discrete Mathematics, v.346, no.2 | - |
dc.relation.isPartOf | Discrete Mathematics | - |
dc.citation.title | Discrete Mathematics | - |
dc.citation.volume | 346 | - |
dc.citation.number | 2 | - |
dc.type.docType | Article | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.isOpenAccess | N | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Mathematics | - |
dc.relation.journalWebOfScienceCategory | Mathematics | - |
dc.subject.keywordPlus | PFAFFIAN ORIENTATIONS | - |
dc.subject.keywordPlus | PERMANENTS | - |
dc.subject.keywordPlus | GRAPHS | - |
dc.subject.keywordPlus | CYCLES | - |
dc.subject.keywordAuthor | Barnette&apos | - |
dc.subject.keywordAuthor | s conjecture | - |
dc.subject.keywordAuthor | Bipartite graphs | - |
dc.subject.keywordAuthor | Cubic graphs | - |
dc.subject.keywordAuthor | Matching theory | - |
dc.subject.keywordAuthor | Perfect matching | - |
dc.subject.keywordAuthor | Pfaffian graphs | - |