{"entities":{"Q2689480":{"pageid":2700223,"ns":120,"title":"Item:Q2689480","lastrevid":47824330,"modified":"2026-01-02T19:25:40Z","type":"item","id":"Q2689480","labels":{"en":{"language":"en","value":"Odd coloring of sparse graphs and planar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7661985"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2689480$15E0274C-9A2E-4E94-AD77-01E9B331ACBD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e70c713c09376cbf304291e66b0f53a1b2bddc31","datavalue":{"value":{"text":"Odd coloring of sparse graphs and planar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2689480$FA0E441A-7121-4E9D-8970-2F56ACF259E2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"008ca0337b5774dfc3a7487823692b420d3ce59a","datavalue":{"value":{"entity-type":"item","numeric-id":2053677,"id":"Q2053677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2689480$096FC9A9-1C08-48CD-996F-3FB2D8DBE6D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5938b4cfed150f2668b98e2677672936728a803c","datavalue":{"value":{"entity-type":"item","numeric-id":400410,"id":"Q400410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2689480$44DE0384-2031-46F1-833B-8955D649F467","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a13bf810bfeac542296da82147f082c73b6f4c05","datavalue":{"value":{"entity-type":"item","numeric-id":2689479,"id":"Q2689479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2689480$0A63B655-B65E-4642-B6C3-70B7BB0A31D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7534a48fbafa87d75d3bec7c1dfe2cad31768c08","datavalue":{"value":{"entity-type":"item","numeric-id":333479,"id":"Q333479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2689480$92B1AC2B-A13D-4158-BE87-081F3F4B8495","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2689480$9B6B36AA-A198-4F40-98BE-05D8897A1E46","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ffed8e8d30c95f79058c35c3950af7927ffd6a67","datavalue":{"value":{"time":"+2023-03-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2689480$07085ADF-8352-4F91-936B-A4D71F7F88C4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3782e266b400acbc3680a9bdb81eafdd10838ecf","datavalue":{"value":"https://arxiv.org/abs/2202.11267","type":"string"},"datatype":"url"},"type":"statement","id":"Q2689480$8A548674-C528-4FB0-9863-8C81C9764293","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2349989d069ba5a248055d23feaf7a8a9d993325","datavalue":{"value":"Let \\(G=(V(G),E(G))\\) be a graph and \\(c:V(G)\\rightarrow \\{1,\\dots,k\\}\\) a proper coloring, i. e., \\(c(u)\\neq c(v)\\) for every \\(uv\\in E(G)\\). If for every vertex \\(v\\) with a degree at least one there exists a color \\(i_v\\in\\{1,\\dots,k\\}\\) that appears an odd number of times in the neighborhood of \\(v\\), then we call \\(c\\) an odd coloring with \\(k\\) colors. Maximum average degree \\(\\mathrm{mad}(G)\\) of \\(G\\) is the biggest average degree of any subgraph of \\(G\\).  This contribution completely resolves Cranston's conjecture that in \\(G\\) there exists an odd coloring with \\(k\\geq 4\\) colors if \\(\\mathrm{mad}(G)\\leq\\frac{4k-4}{k+1}\\). This conjecture is disproved for \\(k=4\\), while for \\(k\\geq 7\\) a stronger version of the conjecture is proved. (The conjecture is already known to be true for \\(k\\in\\{5,6\\}\\).) Some additional results are given for planar graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2689480$EA2AD609-BA87-46D3-AFAF-9307C3F36217","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7fbfd6a9c9db4c04ae1819627a7c5da1a84e5679","datavalue":{"value":{"entity-type":"item","numeric-id":279208,"id":"Q279208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2689480$B6C96B9C-F8B9-4DFC-B2E1-EE7743304FCD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2689480$4486787C-F329-45A8-AA37-FC89A9C1B9EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2689480$B83931EA-9DCE-4FD2-9420-17AA93D56B76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2689480$2468F433-AD90-4EC6-9EFF-1E16CC7739CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2689480$35CEF5F3-9D4E-4000-B358-791DA806976B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dd6f379c67193e2e919a4210d6e72627269b7308","datavalue":{"value":"7661985","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2689480$038F6238-E611-43E1-8EE0-463E76A67EFC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4642cb5f59a32d20bfc2644c3a979efeb720884f","datavalue":{"value":"odd coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2689480$27F44C68-DCEC-4982-B083-9630F9CF213E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"abb3f5ef5bfe0d22c9079f4c5062a5ca51d55e34","datavalue":{"value":"maximum average degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2689480$E3F28A77-CC5F-4CE3-97B4-CD855A69A922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2689480$B521C225-D4C6-4AE2-BC5F-C46B6C926803","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2689480$943C4BAC-8E33-4A03-8CDA-D7199754BA02","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6d84faf2d07d4928231cc7abd37951f0f7e8b0cf","datavalue":{"value":"W4315784453","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2689480$CE3B3FE9-BBC1-4913-B4D8-84EF105776C9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d58b3fc96c8ff695d9353270cca926edc23d8031","datavalue":{"value":{"entity-type":"item","numeric-id":4556952,"id":"Q4556952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2689480$9EFF72A7-BA17-40A7-BC0B-1418112A29D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b7e3c5092ca5330e10b47ed59c693219e1367fa","datavalue":{"value":{"entity-type":"item","numeric-id":2110602,"id":"Q2110602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2689480$5D36B07B-E0F8-4BB4-99FD-862129E27B7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a92ab907df072bb20a1057061523b1fdda43679","datavalue":{"value":{"entity-type":"item","numeric-id":5782525,"id":"Q5782525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2689480$74BBFB74-0F8E-47A0-8437-1FD511A6378A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"225c92174e7c29eb9eb744cd47b5ceaba94b8219","datavalue":{"value":{"entity-type":"item","numeric-id":2172423,"id":"Q2172423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2689480$4A64580D-5C5D-4D71-B750-9DCE77C79128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9964596a6f263ed464de439f5347d02890494490","datavalue":{"value":{"entity-type":"item","numeric-id":2172422,"id":"Q2172422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2689480$66ED7D8C-EC38-4873-ACA7-E7E28F56E11E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9d7c19e93a1ed79e2a12ca0ff121aa9b5f163dce","datavalue":{"value":"10.1016/J.DISC.2022.113305","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2689480$1664F717-AE0C-4424-B4C0-5AFB85291EBD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4aaaa96964b85dbe8818cb2230b1a91cbd7c1cb6","datavalue":{"value":{"entity-type":"item","numeric-id":4811184,"id":"Q4811184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ea51fc258ade4818466d249234c27dd077cba7e","datavalue":{"value":{"amount":"+0.7939404249191284","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2689480$2F3E3B17-2F9F-415F-A2E7-949D4DAA76B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48a6fa01b9ac358228e2d706c6e5d66747150481","datavalue":{"value":{"entity-type":"item","numeric-id":2858018,"id":"Q2858018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a87f3286f23f31189ac1fa4856b059d95b440813","datavalue":{"value":{"amount":"+0.793001651763916","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2689480$9019D30E-10C8-491C-ABB9-6FE83956D81A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a8d60fc37578fccc14d3a740b2631468e28b93f","datavalue":{"value":{"entity-type":"item","numeric-id":5966563,"id":"Q5966563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b78e05052558ae596a52c84a0228415b1ba5462c","datavalue":{"value":{"amount":"+0.7689999938011169","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2689480$3527F57B-C6F3-4F9C-92E7-94637C3F74D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbbbe86a6f84b14f062f160137278616f10a6b50","datavalue":{"value":{"entity-type":"item","numeric-id":1682405,"id":"Q1682405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70d7e760aa4747cca3ac8d0cf3a80c55b73bcd42","datavalue":{"value":{"amount":"+0.7653436064720154","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2689480$3DF5F6E8-B729-4327-9F1C-945015FFBBEC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2689480","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2689480"}}}}}