{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T20:00:46Z","timestamp":1743019246302,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030900472"},{"type":"electronic","value":"9783030900489"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-90048-9_6","type":"book-chapter","created":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T16:03:44Z","timestamp":1635437024000},"page":"59-73","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Barnette\u2019s Conjecture Through the Lens of the $$Mod_{k}P$$ Complexity Classes"],"prefix":"10.1007","author":[{"given":"Robert D.","family":"Barish","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akira","family":"Suyama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,10,29]]},"reference":[{"issue":"2","key":"6_CR1","doi-asserted-by":"publisher","first-page":"781","DOI":"10.4007\/annals.2004.160.781","volume":"160","author":"M Agrawal","year":"2004","unstructured":"Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P. Ann. Math. 160(2), 781\u2013793 (2004)","journal-title":"Ann. Math."},{"key":"6_CR2","unstructured":"Barnette, D.: Conjecture 5. In: Tutte, W.T. (ed.) Recent Problems in Combinatorics, p. 343. Academic Press, New York (1969)"},{"issue":"2\u20133","key":"6_CR3","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0012-365X(84)90074-8","volume":"52","author":"V Batagelj","year":"1984","unstructured":"Batagelj, V.: Inductive definition of two restricted classes of triangulations. Discrete Math. 52(2\u20133), 113\u2013121 (1984)","journal-title":"Discrete Math."},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/3-540-52282-4_31","volume-title":"STACS 90","author":"R Beigel","year":"1990","unstructured":"Beigel, R., Gill, J., Hertramp, U.: Counting classes: thresholds, parity, mods, and fewness. In: Choffrut, C., Lengauer, T. (eds.) STACS 1990. LNCS, vol. 415, pp. 49\u201357. Springer, Heidelberg (1990). https:\/\/doi.org\/10.1007\/3-540-52282-4_31"},{"key":"6_CR5","unstructured":"Bos\u00e1k, J.: Hamiltonian lines in cubic graphs. In: Fiedler, M. (ed.) Proceedings of the International Seminar on Graph Theory and Applications, Rome, July 1966; Appearing in Theory of Graphs, pp. 35\u201346. Gordon & Breach, New York (1967)"},{"issue":"3","key":"6_CR6","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/BF00383444","volume":"8","author":"G Brightwell","year":"1991","unstructured":"Brightwell, G., Winkler, P.: Counting linear extensions. Order 8(3), 225\u2013242 (1991)","journal-title":"Order"},{"key":"6_CR7","unstructured":"Cahit, I.: Algorithmic proof of Barnette\u2019s conjecture. arXiv:0904.3431, pp. 1\u201313 (2009)"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC), pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"},{"key":"6_CR9","unstructured":"Feder, T., Subi, C.: On Barnette\u2019s conjecture. Rep. TR06-015, Electronic Colloquium on Computational Complexity (ECCC) (2006)"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0167-5060(08)70458-8","volume":"41","author":"H Fleischner","year":"1989","unstructured":"Fleischner, H., Jackson, B.: A note concerning some conjectures on cyclically 4-edge connected 3-regular graphs. Ann. Discrete Math. 41, 171\u2013178 (1989)","journal-title":"Ann. Discrete Math."},{"issue":"4","key":"6_CR11","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5(4), 704\u2013714 (1976)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"6_CR12","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0304-3975(86)90165-9","volume":"43","author":"LM Goldschlager","year":"1986","unstructured":"Goldschlager, L.M., Parberry, I.: On the construction of parallel computers from various bases of boolean functions. Theoret. Comput. Sci. 43(1), 43\u201358 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"1131","DOI":"10.1090\/S0002-9904-1970-12601-5","volume":"76","author":"B Grunbaum","year":"1970","unstructured":"Grunbaum, B.: Polytopes, graphs, and complexes. Bull. Amer. Math. Soc. 76, 1131\u20131201 (1970)","journal-title":"Bull. Amer. Math. Soc."},{"issue":"3","key":"6_CR14","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0304-3975(90)90081-R","volume":"74","author":"U Hertrampf","year":"1990","unstructured":"Hertrampf, U.: Relations among Mod-classes. Theoret. Comput. Sci. 74(3), 325\u2013328 (1990)","journal-title":"Theoret. Comput. Sci."},{"key":"6_CR15","unstructured":"Impagliazzo, R.: A personal view of average-case complexity. In: Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT), pp. 134\u2013147 (1995)"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.)Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"6_CR17","unstructured":"Kasteleyn, P.W.: Graph theory and crystal physics. In: Harary, F. (ed.) Graph Theory and Theoretical Physics, pp. 43\u2013110. Academic Press, New York (1967)"},{"issue":"3","key":"6_CR18","first-page":"265","volume":"9","author":"LA Levin","year":"1973","unstructured":"Levin, L.A.: Universal search problems. Probl. Peredachi Inf. 9(3), 265\u2013266 (1973)","journal-title":"Probl. Peredachi Inf."},{"issue":"1\u20133","key":"6_CR19","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0304-3975(03)00080-X","volume":"304","author":"M Li\u015bkiewicz","year":"2003","unstructured":"Li\u015bkiewicz, M., Ogihara, M., Toda, S.: The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. Theoret. Comput. Sci. 304(1\u20133), 129\u2013156 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"13\u201314","key":"6_CR20","doi-asserted-by":"publisher","first-page":"2054","DOI":"10.1016\/j.disc.2010.03.010","volume":"310","author":"X Lu","year":"2010","unstructured":"Lu, X.: A note on 3-connected cubic planar graphs. Discrete Math. 310(13\u201314), 2054\u20132058 (2010)","journal-title":"Discrete Math."},{"issue":"1","key":"6_CR21","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/0095-8956(92)90004-H","volume":"56","author":"W McCuaig","year":"1992","unstructured":"McCuaig, W.: Edge reductions in cyclically k-connected cubic graphs. J. Combin. Theory Ser. B 56(1), 16\u201344 (1992)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"6_CR22","doi-asserted-by":"publisher","first-page":"96","DOI":"10.4064\/fm-10-1-96-115","volume":"10","author":"K Menger","year":"1927","unstructured":"Menger, K.: Zur allgemeinen kurventheorie. Fundam. Math. 10(1), 96\u2013115 (1927)","journal-title":"Fundam. Math."},{"key":"6_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BFb0036487","volume-title":"Theoretical Computer Science","author":"CH Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Zachos, S.K.: Two remarks on the power of counting. In: Cremers, A.B., Kriegel, H.-P. (eds.) GI-TCS 1983. LNCS, vol. 145, pp. 269\u2013275. Springer, Heidelberg (1982). https:\/\/doi.org\/10.1007\/BFb0036487"},{"issue":"2","key":"6_CR24","first-page":"363","volume":"11","author":"S Pirzada","year":"2019","unstructured":"Pirzada, S., Shah, M.A.: Construction of Barnette graphs whose large subgraphs are non-Hamiltonian. Acta Univ. Sapientiae Math. 11(2), 363\u2013370 (2019)","journal-title":"Acta Univ. Sapientiae Math."},{"key":"6_CR25","first-page":"271","volume":"42\u201343","author":"J Plesn\u00edk","year":"1983","unstructured":"Plesn\u00edk, J.: The NP-completeness of the Hamiltonian cycle problem in bipartite cubic planar graphs. Acta Math. Univ. Comenian. 42\u201343, 271\u2013273 (1983)","journal-title":"Acta Math. Univ. Comenian."},{"key":"6_CR26","unstructured":"Seta, T.: The complexities of puzzles, Cross Sum and their Another Solution Problems (ASP). Senior Thesis, Department of Infomation Science, the Faculty of Science, the University of Tokyo (2002)"},{"key":"6_CR27","unstructured":"Steinitz, E.: Polyeder und raumeinteilungen. Encyklopadie der mathematischen Wissenschaften. Bd. III-1B, Hft. 9, pp. 1\u2013139 (1922)"},{"issue":"2","key":"6_CR28","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1112\/jlms\/s1-21.2.98","volume":"s1\u201321","author":"WT Tutte","year":"1946","unstructured":"Tutte, W.T.: On Hamiltonian circuits. J. London Math. Soc. s1\u201321(2), 98\u2013101 (1946)","journal-title":"J. London Math. Soc."},{"issue":"2","key":"6_CR29","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoret. Comput. Sci. 8(2), 189\u2013201 (1979)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"6_CR30","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"key":"6_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11533719_1","volume-title":"Computing and Combinatorics","author":"LG Valiant","year":"2005","unstructured":"Valiant, L.G.: Completeness for parity problems. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 1\u20138. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11533719_1"},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Accidental algorithms. In: Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS), pp. 509\u2013517 (2006)","DOI":"10.1109\/FOCS.2006.7"},{"issue":"1","key":"6_CR33","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"LG Valiant","year":"1986","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. Theoret. Comput. Sci. 47(1), 85\u201393 (1986)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"6_CR34","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1142\/S0129054191000066","volume":"2","author":"V Zank\u00f3","year":"1991","unstructured":"Zank\u00f3, V.: #P-completeness via many-one reductions. Int. J. Found. Comput. Sci. 2(1), 77\u201382 (1991)","journal-title":"Int. J. Found. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Discrete and Computational Geometry, Graphs, and Games"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-90048-9_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T16:05:13Z","timestamp":1635437113000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-90048-9_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030900472","9783030900489"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-90048-9_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"29 October 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"JCDCGGG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japanese Conference on Discrete and Computational Geometry, Graphs, and Games","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Quezon City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Philippines","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 September 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 September 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"jcdcg2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ateneo.edu\/ls\/sose\/mathematics\/jcdcggg2018","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}