乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,24]],"date-time":"2023-11-24T19:40:07Z","timestamp":1700854807300},"reference-count":36,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2021,9,24]],"date-time":"2021-09-24T00:00:00Z","timestamp":1632441600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2022,2]]},"abstract":"Abstract<\/jats:title>We define a family of vertex colouring games played over a pair of graphs or digraphs by players and . These games arise from work on a longstanding open problem in algebraic logic. It is conjectured that there is a natural number such that always has a winning strategy in the game with colours whenever . This is related to the reconstruction conjecture for graphs and the degree\u2010associated reconstruction conjecture for digraphs. We show that the reconstruction conjecture implies our game conjecture with for graphs, and the same is true for the degree\u2010associated reconstruction conjecture and our conjecture for digraphs. We show (for any ) that the 2\u2010colour game can distinguish certain nonisomorphic pairs of graphs that cannot be distinguished by the \u2010dimensional Weisfeiler\u2013Leman algorithm. We also show that the 2\u2010colour game can distinguish the nonisomorphic pairs of graphs in the families defined by Stockmeyer as counterexamples to the original digraph reconstruction conjecture.<\/jats:p>","DOI":"10.1002\/jgt.22741","type":"journal-article","created":{"date-parts":[[2021,9,24]],"date-time":"2021-09-24T22:59:57Z","timestamp":1632524397000},"page":"278-311","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Seurat games on Stockmeyer graphs"],"prefix":"10.1002","volume":"99","author":[{"given":"Rob","family":"Egrot","sequence":"first","affiliation":[{"name":"Computer Science Academic Group, Faculty of Information And Communication Technology Mahidol University Bangkok Thailand"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-2983-4178","authenticated-orcid":false,"given":"Robin","family":"Hirsch","sequence":"additional","affiliation":[{"name":"Department of Computer Science University College London London UK"}]}],"member":"311","published-online":{"date-parts":[[2021,9,24]]},"reference":[{"key":"e_1_2_9_2_1","doi-asserted-by":"crossref","unstructured":"J. A.Bondy A graph reconstructor's manual Surveys in combinatorics (Guildford 1991) London Math. Soc. Lecture Note Ser vol. 166 Cambridge University Press Cambridge 1991 pp. 221\u2013252.","DOI":"10.1017\/CBO9780511666216.009"},{"key":"e_1_2_9_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_2_9_4_1","unstructured":"L.Chinand\u00a0A.Tarski Distributive and modular laws in the arithmetic of relation algebras Univ. California Publ. Math. (N.S.) Vol. 1 University of California Press Berkeley CA 1951."},{"key":"e_1_2_9_5_1","unstructured":"B.CourcelleandJ.Engelfriet Graph structure and monadic second\u2010order logic: A language\u2010theoretic approach with a foreword by Maurice Nivat Encyclopedia of Mathematics and its Applications vol. 138 \u00a0Cambridge University Press Cambridge 2012."},{"key":"e_1_2_9_6_1","unstructured":"R.EgrotandR.Hirsch First\u2010order axiomatisations of representable relation algebras need formulas of unbounded quantifier depth.2020.https:\/\/arxiv.org\/abs\/2008.01329"},{"key":"e_1_2_9_7_1","unstructured":"R.EgrotandR.Hirsch A corrected strategy for proving no finite variable axiomatisation exists for RRA 2021.\u00a0https:\/\/arxiv.org\/abs\/2109.01357"},{"key":"e_1_2_9_8_1","doi-asserted-by":"crossref","unstructured":"M.Grohe Descriptive complexity canonisation and definable graph structure theory Lecture Notes in Logic vol. 47 Association for Symbolic Logic Ithaca NY; Cambridge University Press Cambridge 2017.","DOI":"10.1017\/9781139028868"},{"key":"e_1_2_9_9_1","doi-asserted-by":"crossref","unstructured":"F.Harary A survey of the reconstruction conjecture Graphs and combinatorics (Proc. Capital Conf. George Washington Univ. Washington D.C. 1973) Lecture Notes in Math. vol. 406 1974 pp. 18\u201328.","DOI":"10.1007\/BFb0066431"},{"key":"e_1_2_9_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00085-9"},{"key":"e_1_2_9_11_1","volume-title":"Relation Algebras by Games","author":"Hirsch R.","year":"2002"},{"key":"e_1_2_9_12_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-04-03743-2"},{"key":"e_1_2_9_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"e_1_2_9_14_1","unstructured":"N.ImmermanandR.Sengupta Thek\u2010dimensional Weisfeiler\u2010Leman Algorithm ArXiv.2019."},{"key":"e_1_2_9_15_1","unstructured":"B.J\u00f3nsson The theory of binary relations Algebraic logic (Budapest 1988) Colloq. Math. Soc. J\u00e1nos Bolyai vol. 54 North\u2010Holland Amsterdam 1991 pp. 245\u2013292."},{"issue":"80","key":"e_1_2_9_16_1","first-page":"1192","article-title":"Representation problems for relation algebras","volume":"54","author":"J\u00f3nsson B.","year":"1948","journal-title":"Bull. Amer. Math. Soc."},{"key":"e_1_2_9_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3436980.3436982"},{"key":"e_1_2_9_18_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-8-1-114-134"},{"key":"e_1_2_9_19_1","doi-asserted-by":"crossref","unstructured":"J.Lauri andR.Scapellato Topics in graph automorphisms and reconstruction London Mathematical Society Lecture Note Series vol. 432 2nd ed. Cambridge University Press Cambridge 2016.","DOI":"10.1017\/CBO9781316669846"},{"key":"e_1_2_9_20_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Texts in Theoretical Computer Science. An EATCS Series","author":"Libkin L.","year":"2004"},{"key":"e_1_2_9_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969375"},{"key":"e_1_2_9_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/2274756"},{"key":"e_1_2_9_23_1","unstructured":"R.Maddux Relation algebras Studies in Logic: the Foundations of Mathematics \u00a0vol. 150 Elsevier 2006."},{"key":"e_1_2_9_24_1","unstructured":"R. D.Maddux Topics in Relation Algebra. Ph.D. Thesis University of California Berkeley 1978."},{"issue":"3","key":"e_1_2_9_25_1","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1007\/BF00370681","article-title":"The origin of relation algebras in the development and axiomatization of the calculus of relations","volume":"50","author":"Maddux R. D.","year":"1991","journal-title":"Studia Logica: Int J Symbolic Logic."},{"key":"e_1_2_9_26_1","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1028999131"},{"key":"e_1_2_9_27_1","doi-asserted-by":"publisher","DOI":"10.2307\/2316851"},{"key":"e_1_2_9_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(81)80019-6"},{"key":"e_1_2_9_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90122-X"},{"key":"e_1_2_9_30_1","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1130335206"},{"key":"e_1_2_9_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190010108"},{"key":"e_1_2_9_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(81)80027-5"},{"key":"e_1_2_9_33_1","unstructured":"P. K.Stockmeyer Tilting at windmills or My quest for nonreconstructible graphs 250th Anniversary Conference on Graph Theory (Fort Wayne IN 1986) vol. 63 1988 pp. 188\u2013200."},{"key":"e_1_2_9_34_1","doi-asserted-by":"publisher","DOI":"10.2307\/2268577"},{"key":"e_1_2_9_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1385-7258(55)50009-6"},{"key":"e_1_2_9_36_1","doi-asserted-by":"crossref","unstructured":"A.TarskiandS.Givant A formalization of set theory without variables. Number 41 in Colloquium Publications. Amer. Math. Soc. Providence RI 1987.","DOI":"10.1090\/coll\/041"},{"key":"e_1_2_9_37_1","volume-title":"Interscience Tracts in Pure and Applied Mathematics","author":"Ulam S. M.","year":"1960"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22741","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/jgt.22741","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22741","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,28]],"date-time":"2023-08-28T03:15:25Z","timestamp":1693192525000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.22741"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,24]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["10.1002\/jgt.22741"],"URL":"https:\/\/doi.org\/10.1002\/jgt.22741","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,24]]},"assertion":[{"value":"2021-05-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-20","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}