{"entities":{"Q6133668":{"pageid":13267975,"ns":120,"title":"Item:Q6133668","lastrevid":102423422,"modified":"2026-06-06T04:25:31Z","type":"item","id":"Q6133668","labels":{"en":{"language":"en","value":"Proper edge colorings of Cartesian products with rainbow \\(C_4\\)-s"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7730255"}},"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":"Q6133668$7E26C2BE-49A0-43F9-A822-CB9FA4DAB334","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c6491e19a59e94e1694f8f2b5381c9926b4f1066","datavalue":{"value":{"text":"Proper edge colorings of Cartesian products with rainbow \\(C_4\\)-s","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6133668$93865826-6806-45B4-862B-01F02C6C21A1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d548872f2ee1aba2039df65ec881fb6aa2c49cde","datavalue":{"value":"1527.05067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6133668$1295D441-AC08-4614-B31A-42DDA61151AD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3155ff163c931be8945149a68c11d68da0b397d6","datavalue":{"value":{"entity-type":"item","numeric-id":228779,"id":"Q228779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133668$0E4792C2-3F66-4621-982A-231FDC0C7A82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e2f3fdbf9f8c798d03777e6ed3c1ca10e41eb29d","datavalue":{"value":{"entity-type":"item","numeric-id":190556,"id":"Q190556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133668$05D16818-6AA9-4946-B68A-C0CE3589490F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133668$C5F5C331-B55B-47E2-BBC8-76B6955195D6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4b435be9e480714ca524ba5b8a4f1e43894a87ad","datavalue":{"value":{"time":"+2023-08-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6133668$4CA58696-57D5-42F4-BBAA-46ACAD2F767C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5808e7de99b5824491a70e8d94b2109818510888","datavalue":{"value":"The famous Brown-Erd\u0151s-S\u00f3s conjecture (BES-conjecture) assert that if a \\(3\\)-uniform hypergraph (\\(3\\)-graph) \\(H\\) on \\(n\\) vertices does not contain \\(k\\) edges on at most \\(k+3\\) vertices then it has \\(o(n^{2})\\) edges [\\textit{W. G. Brown} et al., in: F. Harary (ed.), New directions in the theory of graphs. Proceedings of the third Ann Arbor conference on graph theory. New York, London: Academic Press. 53--63 (1973; Zbl 0258.05132)]. \\textit{I. Z. Ruzsa} and \\textit{E. Szemer\u00e9di} [Colloq. Math. Soc. J\u00e1nos Bolyai 18, 939--945 (1978; Zbl 0393.05031)] stated that if a \\(3\\)-uniform hypergraph (or shortly \\(3\\)-graph) \\(H\\) on \\(n\\) vertices does not contain \\(3\\) edges on at most \\(6\\) vertices then it has \\(o(n^{2})\\) edges. Moreover, the \\((7, 4)\\)-problem is a spectral case of the BES conjecture and it claims that:  Conjecture. Assume that a \\(3\\)-graph \\(H\\) on \\(n\\) vertices does not contain \\(4\\) edges on at most \\(7\\) vertices (briefly we say that \\(H\\) is \\((7, 4)\\)-free). Then \\(|e(H)|=o(n^{2})\\).   An edge coloring of a graph \\(G\\) is called a rainbow coloring if the edges of every quadrangle (\\(C_{4}\\)) of \\(G\\) are colored with distinct colors. An edge coloring of a graph \\(G\\) is proper if incident edges of \\(G\\) must receive different colors. Based on these, the authors define proper rainbow coloring as \\(B\\)-coloring and write \\(q_{B}(G)\\) for the smallest number of colors needed for a \\(B\\)-coloring of a graph \\(G\\).  In this paper, the authors consider \\(q_{B}(G)\\) for Cartesian products of paths and cycles. Their main tool is a lemma which provides that \\(q_{B}(G\\square H) \\leq q_{B}(G) + q_{B}(H)\\) if \\(\\chi(G) \\leq q_{B}(H)\\), \\(\\chi(H) \\leq q_{B}(G)\\), where \\(\\chi(G)\\) is the chromatic number of \\(G\\). Furthermore, \\(B\\)-coloring is similar to the well-studied concept of star-edge colorings, which is also related to the \\((7,4)\\)-problem. So the results of this paper provide a positive answer to the \\((7,4)\\)-problem in some sense. All the certification procedures are strict, and the ways of proof are properly novel.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6133668$D8E9DC28-266B-4E88-89E0-E38C67D283A2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"65c60d61f28dd59acd06fc7e6e4f31afc3b007cf","datavalue":{"value":{"entity-type":"item","numeric-id":308315,"id":"Q308315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133668$B0EF63D6-755F-4A21-AE3D-4DB48F833C83","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6133668$7638D586-1C82-4909-88D8-2FE8FA324037","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f54624d6184313158324a5b5a097f6e611a50ba5","datavalue":{"value":"05C76","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6133668$51382925-2332-40A0-9DDD-4C039EA28B61","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6ba7f2141b933475118bc95896cc4d8dd18acea9","datavalue":{"value":"7730255","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6133668$899C8AB0-F7D7-4D39-9B76-8B47DA665EF4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e02710f05cb213989d5adae74bf79048ad1756f9","datavalue":{"value":"proper edge colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q6133668$037D41BF-2E8D-4B45-A17A-909E2DDB9C14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"509f4d170b3208e5a7d8bbe2a11b277ec94406a5","datavalue":{"value":"rainbow colorings of four-cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q6133668$353DA65E-A938-4465-ABEA-178345465AF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3d009c78b4a6a98a7e969740d48b52bd7730b8d","datavalue":{"value":"grid graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6133668$B817B976-5034-4BC5-82D1-E193C14B824B","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":"Q6133668$D73049E8-DFBE-4AE9-9018-9C5D6C10D77B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"20d201df3525dacccca5e636a4670df3c798f03f","datavalue":{"value":{"entity-type":"item","numeric-id":4916092,"id":"Q4916092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133668$1EE5724E-C9B6-484E-93B8-200A38ED5310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56d7addad14022a6b3b4f87a4e098181ff3b1075","datavalue":{"value":{"entity-type":"item","numeric-id":1280270,"id":"Q1280270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133668$227E6236-2AA2-43AC-A973-FD152BBC8DF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b244fda6a204a156785b97b4248af777add1a2e","datavalue":{"value":{"entity-type":"item","numeric-id":4271617,"id":"Q4271617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133668$2E3E084F-888E-4FB8-BF80-CB2F5B57ECB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99983275526cf2096a673294969ba0016878096c","datavalue":{"value":{"entity-type":"item","numeric-id":4715283,"id":"Q4715283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133668$79D00B8C-D8B7-4369-87F3-E8FC8F32AAE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b26503107f71a5e9fc851008aba2292ac5c09c45","datavalue":{"value":{"entity-type":"item","numeric-id":4998163,"id":"Q4998163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133668$045AB4B8-7122-461F-91D0-61133D5E517C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5df241cdfc2b20b92c39cef893b780873863ab68","datavalue":{"value":{"entity-type":"item","numeric-id":3246727,"id":"Q3246727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133668$7BD14ED6-2177-47DF-9140-6311FA43CBD3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bdd51379a2e01fac8920bf35f81c89826c739d81","datavalue":{"value":"10.1007/S00373-023-02697-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6133668$83C42D20-F7F4-4078-9C7E-91FEDABD8AA2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcc73634addbfd7bc2db94556104d76bbb489330","datavalue":{"value":{"entity-type":"item","numeric-id":383748,"id":"Q383748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ec8945972c9700b10c9ed32fa390593de52c2ae","datavalue":{"value":{"amount":"+0.9126911","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6133668$80C2006D-8956-46FA-9283-50B80D09DED4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1383b57d24c831d09312e627db933a8eb1f7877","datavalue":{"value":{"entity-type":"item","numeric-id":2005704,"id":"Q2005704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b899445813bd1fd20dd92abc9442736063111eff","datavalue":{"value":{"amount":"+0.91028947","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6133668$8E9F6969-5E38-48D1-81DF-02BC0FE46A8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee5cdb79a7b35359bb115c400c58bb8a10a2e015","datavalue":{"value":{"entity-type":"item","numeric-id":299042,"id":"Q299042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed8d4db94e696520395ed07669463fb25315f203","datavalue":{"value":{"amount":"+0.8968847","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6133668$299426D1-6B14-4F05-9044-9D0B620FDBB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65d6bab340f7b3d4082bd482eea81cbfaa6991fe","datavalue":{"value":{"entity-type":"item","numeric-id":4393386,"id":"Q4393386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d2410d8ba912ae4f4ac6e4738b44dab6c1f0128","datavalue":{"value":{"amount":"+0.88863933","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6133668$2133CA7F-9123-4CAA-B624-5F81119705BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a93ccd1e86aa02bfe1b73241db2faaababd56a3","datavalue":{"value":{"entity-type":"item","numeric-id":5087858,"id":"Q5087858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c296e966abee96e3bf308ba1c536bcf442e24c39","datavalue":{"value":{"amount":"+0.8857315","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6133668$5659630F-DB39-4CBC-89B6-2E1EC97CCC5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ee28cd6cd6dfad7771968e71d54e285beff7017","datavalue":{"value":{"entity-type":"item","numeric-id":3686733,"id":"Q3686733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41ed8957712f9edf8c72a9323b0ff6c95dd417f3","datavalue":{"value":{"amount":"+0.8846087","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6133668$46FDAC84-8B78-4342-9993-F82513A9EECF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"826433a0880ec5c2da6ad8dccc12ae7bbc3734cb","datavalue":{"value":{"entity-type":"item","numeric-id":2368384,"id":"Q2368384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7943d8d43ba1eed9bd4f1d443c3b4d30801545d2","datavalue":{"value":{"amount":"+0.88035196","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6133668$1424198B-615A-4870-BA0A-E7D33C18A7F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e349c52629bfa6b8e24839b8c0acb231da3f060e","datavalue":{"value":{"entity-type":"item","numeric-id":2857036,"id":"Q2857036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba8ef1f2529ffb8076d4c2d1356cc0f8c1f72173","datavalue":{"value":{"amount":"+0.8792939","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6133668$63D84E4B-0874-46C2-A14F-C67909A7B0AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6a98b4cdaf11a78b87d204ce1dd90f306b46c66","datavalue":{"value":{"entity-type":"item","numeric-id":3439562,"id":"Q3439562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39f712933dc0aa5f5bb15ab72dff3a6c8caf52c2","datavalue":{"value":{"amount":"+0.877916","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6133668$46AB3931-377E-4CFF-85CD-2D8A2D944CB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3c8a29542a68311530331af5b1733f15fcc3b65","datavalue":{"value":{"entity-type":"item","numeric-id":5036728,"id":"Q5036728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c007fecd6435039669fa2f16f1862536ceb2e96","datavalue":{"value":{"amount":"+0.87773794","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6133668$90A01DBF-2D0A-40FC-92A5-D7FBFA3088AF","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133668$AFA41CEA-2B52-472E-9D6F-8CB34E90EC70","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Proper edge colorings of Cartesian products with rainbow \\(C 4\\)-s","badges":[]}}}}}