{"entities":{"Q708380":{"pageid":710229,"ns":120,"title":"Item:Q708380","lastrevid":51101057,"modified":"2026-01-16T16:28:35Z","type":"item","id":"Q708380","labels":{"en":{"language":"en","value":"Coloring the square of the Cartesian product of two cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5798527"}},"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":"Q708380$D3795F16-10D9-41E8-9CD6-948D9203ED84","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"efbeb141d1ef7d25a761cf5b693748772ad1b85f","datavalue":{"value":{"text":"Coloring the square of the Cartesian product of two cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q708380$7E98A09F-8E5A-4407-98C0-128F1E8C3AA8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"072b3193fba05cfbfb82af084c13d7cf8edd8936","datavalue":{"value":"1213.05101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q708380$F52E6C26-4827-4B77-9323-6BBA3DFE5923","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"956ba4b8944430d4806db40dd0f71d20c580aa10","datavalue":{"value":{"entity-type":"item","numeric-id":449197,"id":"Q449197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$68AEA9AC-BA14-4E42-AADF-D1A5CE467F0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a34d7460ee6370363f9008097bc89d9a4353ddd3","datavalue":{"value":{"entity-type":"item","numeric-id":175612,"id":"Q175612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$B026E095-63AB-4A35-ABD3-418EE74E4443","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":"Q708380$F4580CA6-10F0-4DEE-B732-10B6D6D9DBF7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0f64b28384ad68ec83e16fec2c0efbccc5663b19","datavalue":{"value":{"time":"+2010-10-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q708380$869F5EA7-61F8-41A1-B695-713C52E24CF5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6c5416d7fd7a5ba9534c166bb66269fa6f8124a2","datavalue":{"value":"The \\textit{square} \\(G^2\\) of a graph \\(G\\) is given by \\(V(G^2)=V(G)\\) and \\(\\{u,v\\} \\in E(G^2)\\) if and only if \\(\\{u,v\\} \\in E(G)\\) or \\(u\\) and \\(v\\) have a common neighbour. The Cartesian product \\(G \\square H\\) of given graphs \\(G\\) and \\(H\\) is the graph with vertex set \\(V(G)\\times V(H)\\) where two vertices \\((u_1, v_1)\\) and \\((u_2, v_2)\\) are adjacent if and only if either \\(u_1=u_2\\) and \\(\\{v_1,v_2\\}\\in E(H)\\) or \\(v_1=v_2\\) and \\(\\{u_1,u_2\\}\\in E(G)\\). It is shown that the chromatic number of the Cartesian product \\(C_m\\square C_n\\) of two cycles is at most 7 except when \\((m,n)\\) is \\((3, 3)\\), in which case the value is 9, and when \\((m, n)\\) is \\((4, 4)\\) or \\((3, 5)\\), in which case the value is 8. Moreover, it is conjectured that whenever \\(G=C_m\\square C_n\\), the chromatic number of \\(G^2\\) equals \\(\\lceil mn/ \\alpha(G^2)\\rceil\\), where \\(\\alpha(G^2)\\) denotes the maximum size of an independent set in \\(G^2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q708380$EA87DC14-5CB3-4D57-8C44-A59A7D90B394","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q708380$50A48895-CDA8-4FBC-B468-164141D3B7CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f54624d6184313158324a5b5a097f6e611a50ba5","datavalue":{"value":"05C76","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q708380$353707A4-B45A-4D1A-A79D-884B83E7F3A5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1cb4b141172a74aa3b07929b4d6ab6ab0cc4e5b3","datavalue":{"value":"5798527","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q708380$D6C10EE5-11BE-453C-9F45-34735E3C5630","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q708380$A58288CA-EA6D-406F-926E-881B74FD8537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9691f6eb53b350bb6f9f4b1d5c81a77010e2c590","datavalue":{"value":"square of graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q708380$F9DDE682-5FFB-4245-9B82-313463175D13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"113d159f95340961c8aca839d6af5d6e14d00be6","datavalue":{"value":"distance 2-colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q708380$E7F28528-CDA7-44EE-955B-04188D628071","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7642d8b032ac6ec79fcbf380f24fdc21e9f421e","datavalue":{"value":"Cartesian product","type":"string"},"datatype":"string"},"type":"statement","id":"Q708380$9FB6585A-0B69-4C98-8732-9043C6F7C773","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ae6cc52b35d03b83d5162d854c61cf5b039329e","datavalue":{"value":"cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q708380$4E89A0D1-2C86-4B86-9BF4-AFE06E28CA40","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af45ac16b5c3b4cb5ad35340a1e807846a86d0e0","datavalue":{"value":{"entity-type":"item","numeric-id":593274,"id":"Q593274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$939D8B37-4961-4A62-ACDA-79391D4888FA","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":"Q708380$C9D36B87-1339-4345-8B54-BB85622DAE88","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e435b6b357a5479d20512d3a95c6a6dc5390dbe1","datavalue":{"value":"https://doi.org/10.1016/j.disc.2010.05.011","type":"string"},"datatype":"url"},"type":"statement","id":"Q708380$DA00EAE6-0BDA-4AAF-AD86-89E831C72C49","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ec41d8db6520f373cb432e7c3ca2e683521bccd1","datavalue":{"value":"W2080714490","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q708380$0680FB4B-1DF4-4CE7-B32B-B97B88B7D0F3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9bea63eab82901ee86b09b2ec8f4d8e9365b1a20","datavalue":{"value":{"entity-type":"item","numeric-id":1005229,"id":"Q1005229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$43DA4039-4716-450B-BFA0-76169C7577ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24df1080a8ad51e61e7a2196b6318c9b21197e2d","datavalue":{"value":{"entity-type":"item","numeric-id":2427536,"id":"Q2427536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$6915F153-067F-4698-8C6E-24E285EFAE0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c01c44950b85395be4d65d72ca0c9528f5ea542","datavalue":{"value":{"entity-type":"item","numeric-id":2706187,"id":"Q2706187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$B2C1030A-60CE-4FFD-879C-727BCFDBF859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a415e76a6c4dfffab8c5043c692bae1e05da99b","datavalue":{"value":{"entity-type":"item","numeric-id":4030197,"id":"Q4030197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$DF48341C-702F-4072-81C8-648422940926","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a47755a3f68d46fd9769f68d415454c70926e0a","datavalue":{"value":{"entity-type":"item","numeric-id":3503513,"id":"Q3503513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$B68B303A-159B-4DB6-8D5F-5F56BF72D72A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a23d59807f3fa7ea92681384d3137199c6493559","datavalue":{"value":{"entity-type":"item","numeric-id":2724308,"id":"Q2724308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$28EDD4DA-22A9-42AD-BAB3-4225EAC87583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f15982b50566a89619d6d0132f554f8a811000b1","datavalue":{"value":{"entity-type":"item","numeric-id":2576352,"id":"Q2576352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$75C247A4-2423-4705-A1B7-F72B142833AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59d5180eea74f4778f7bdb0f1d88e7577493e0d4","datavalue":{"value":{"entity-type":"item","numeric-id":4552180,"id":"Q4552180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$29DB9003-78A0-489B-90E4-8F94A4EB20CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736c926e192b785fd669ff5513f4a77a365dff74","datavalue":{"value":{"entity-type":"item","numeric-id":1827783,"id":"Q1827783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$01ADF3CA-3041-4833-AFBC-49CBB2B116BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4ff7b25bae9339c3413c3d3b8e9e76b3029f608","datavalue":{"value":{"entity-type":"item","numeric-id":2472571,"id":"Q2472571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$E1F6860F-0B19-4EEA-8B40-27AA4BBD67DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5763401a400275883d373fb2cb7e9062551b4b86","datavalue":{"value":{"entity-type":"item","numeric-id":2485944,"id":"Q2485944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$F66069B1-A982-43F9-BD50-5713FA8FCEFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c094516f52221e393c6a14241c16a811843202","datavalue":{"value":{"entity-type":"item","numeric-id":3439562,"id":"Q3439562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$FA72C25F-D760-4E67-ADEA-DB4D58C8F13A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e673b5f5e726472d2b88c9aa01f5357df0c532f9","datavalue":{"value":{"entity-type":"item","numeric-id":2492228,"id":"Q2492228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$563274BF-5478-415B-87E2-3D06917D01E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe2dcd19a03014335d79842ee4ced55daecaa909","datavalue":{"value":{"entity-type":"item","numeric-id":4797924,"id":"Q4797924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$968D91ED-6056-47CA-8AA3-E8EF1F9DA6B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c0bdc13b7ae115bf84ac5dc224b0b308b85c2c7","datavalue":{"value":{"entity-type":"item","numeric-id":4863972,"id":"Q4863972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q708380$62E39998-A171-42C6-9FC0-E9841AE05A8B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bec20e5702c444595d08a1d530a20197a51b218e","datavalue":{"value":"10.1016/J.DISC.2010.05.011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q708380$61B9EF46-A423-46A1-9B1C-B3C44298A4E7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fc204f5e936e75ef569c70c0d6893b87d6ab9ba","datavalue":{"value":{"entity-type":"item","numeric-id":1947008,"id":"Q1947008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10b6a64f9c3c8477f2ad2db97fe8afcd750b5679","datavalue":{"value":{"amount":"+0.9265314340591432","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":"Q708380$8245180E-5D0C-415C-A386-453AE2FA02D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6da5d826f226da6fc119c868d9617487b2fae5dd","datavalue":{"value":{"entity-type":"item","numeric-id":898088,"id":"Q898088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99ad791faf2fac6285f185d5e74ba04187657122","datavalue":{"value":{"amount":"+0.910259246826172","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":"Q708380$445231F1-7F7A-4E50-B210-9A3BDD8C8B0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27260850cb3ad905986942bbf1341c98eb8740c7","datavalue":{"value":{"entity-type":"item","numeric-id":3089292,"id":"Q3089292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"406fc08c6a0d7347d0aed385fe0c01b6c464446f","datavalue":{"value":{"amount":"+0.8814890384674072","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":"Q708380$52AA9788-3A3C-4045-A8F0-7A21ABBB1583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0536344261eba7fb730013c7a668071ba036c82","datavalue":{"value":{"entity-type":"item","numeric-id":3180915,"id":"Q3180915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4060a859f8078861394ca0d5f4930d5bf5befb68","datavalue":{"value":{"amount":"+0.8483688831329346","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":"Q708380$08544990-C60B-46B2-BFFA-3B1DF5050714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9fc71de2e4baca186779f2a109a47d1509158613","datavalue":{"value":{"entity-type":"item","numeric-id":4982919,"id":"Q4982919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b132fd3e44a00bb74834734085af93f19f6be071","datavalue":{"value":{"amount":"+0.8205350637435913","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":"Q708380$A61203F2-BB05-45FB-BFA3-07CD746CD417","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:708380","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:708380"}}}}}