{"entities":{"Q1356483":{"pageid":1367222,"ns":120,"title":"Item:Q1356483","lastrevid":43053848,"modified":"2025-07-17T06:55:26Z","type":"item","id":"Q1356483","labels":{"en":{"language":"en","value":"Defining sets in vertex colorings of graphs and latin rectangles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1018533"}},"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":"Q1356483$778B08D9-02F6-45C6-89FA-21FB15A1F8DE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"674384eb71fd67e32dfcc47f6cc075de435d8a01","datavalue":{"value":{"text":"Defining sets in vertex colorings of graphs and latin rectangles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1356483$2C7D0A7F-D8DE-4909-9572-E74053AC3347","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a5e406e877358532bbf75a2941996acc1fffe5e1","datavalue":{"value":"0879.05028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356483$56C3093A-19CD-4044-A2A6-A0FB0A4EB9E5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bd1f597ec174bd8fce68b46c27b13845451a209a","datavalue":{"value":"10.1016/S0012-365X(96)00247-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356483$4F9D4FFD-DBD4-44BA-9429-00EB53E38CDC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"44300321d1fbc7a188b198a9146b9d790e3a4aa7","datavalue":{"value":{"entity-type":"item","numeric-id":184675,"id":"Q184675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356483$459BB271-6942-4A97-BCB3-5357B7E19194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b66e7e7433a273d8b90445b97e8b5a6dcb77bb5","datavalue":{"value":{"entity-type":"item","numeric-id":260060,"id":"Q260060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356483$5AEC3021-0993-4BBB-9618-93920C8020D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e506ad5e786f00a0c812d88ca395e50eba91ce78","datavalue":{"value":{"entity-type":"item","numeric-id":322366,"id":"Q322366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356483$CB5ACC91-6DCA-4753-B0E5-268B991638C6","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":"Q1356483$9DC7AF9A-D60E-4268-B35E-3F78C6C6D07D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ad4ab8f37a90ca87e9ccd9974f355802c12e0ef2","datavalue":{"value":{"time":"+1998-01-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1356483$D5F8700E-4FB8-4360-B242-C46A75DA8CE9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a1b4c36e0c448bf69ecfa328dab8ebc4a962cede","datavalue":{"value":"A set \\(S\\) of vertices of a graph \\(G\\) is called a defining set of vertex colourings of \\(G\\) if there exists a proper colouring \\(\\varphi\\) of \\(S\\) using \\(k\\leq \\chi(G)\\) colours such that \\(\\varphi\\) has a unique extension to a \\(\\chi (G)\\)-colouring of \\(G\\). The cardinality of a minimum defining set of \\(G\\) is denoted by \\(d_v (G)\\). A critical set in an \\(m \\times n\\) array, \\(m\\leq n\\), is a set \\(S\\) of cells which are preoccupied with \\(k\\leq n\\) symbols such that there is a unique extension of \\(S\\) to a latin rectangle of size \\(m\\times n\\).   Some lower bounds for \\(d_v (G)\\) are obtained and used to show that  \\[ \\begin{aligned} d_v & (K_2 \\times C_{2n+1}) = n+1; \\\\ d_v & (C_m \\times K_n)= m(n-3) \\text{ for }n \\geq 6; \\\\ d_v & (P_m \\times K_n) =m(n-3) +2 \\text{ for } n\\geq 6; \\text{ and} \\\\ d_v & (K_m \\times K_n) =m(n-m) \\text{ if }n \\geq m^2, \\end{aligned}  \\]  where \\(P_m \\times K_n\\) is the Cartesian product of \\(K_2\\) and \\(C_{2n+1}\\).   The authors also determine the size of smallest critical sets of a back circulant latin rectangle of size \\(m\\times n\\), with \\(2m\\leq n\\). It is conjectured that for any latin square of order \\(n\\), the size of a critical set is at least \\(\\lfloor {n^2 \\over 4} \\rfloor\\).   Reviewer's remark: Thayer Morrill and Dan Pritikin have studied defining sets and list-defining sets \\(S\\) in graphs in a slightly broader sense that a proper \\(k\\)-colouring \\(\\varphi\\) of \\(S\\) has a unique extension to a proper \\(k\\)-colouring of \\(G\\), where \\(\\Delta (G)\\leq k\\leq \\Delta (G)+1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356483$F2019641-D6D8-4E39-960C-E7B967BDCAF3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356483$CC5B2ADD-6DE9-46E1-B125-E84543284BDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0fb5c2b5135b23a64eead86c75bb584d8442d720","datavalue":{"value":"05B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356483$19549136-C29B-46A5-9E3A-9CE7292FEDD6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"71e8d37ee2b71bf8c6455f7d755fd5ae2941834d","datavalue":{"value":"1018533","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356483$BB1BF51E-7C0C-4778-9AB7-6346ED26CDC0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e85c6ea8220e137960d352ca7bc5f31d1d34db63","datavalue":{"value":"defining set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356483$313F23E7-66A5-4EF1-9AB3-E6601AAAC06C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a61866b28ef67a30472e3ee08657696fe272f4","datavalue":{"value":"vertex colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356483$480AD216-E222-4039-A26E-4C74573C6DC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d429947695a58848653d815a4887e71963248f3e","datavalue":{"value":"critical set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356483$F42967B6-D313-4634-83DF-5BEAB745F907","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5c01f429063e2cd732d13d035f50e86b1c2faa1b","datavalue":{"value":"latin rectangle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356483$03D85AE8-A07F-4292-8FD3-9EE4E6B4FA57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db883911d6e545b99baee4c131abe809025926b6","datavalue":{"value":"latin square","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356483$A4264895-5A0A-4E41-A86F-BB36F930845E","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"fe952c59a2ebc25f8650e2ab04b8fae0084e3093","datavalue":{"value":"Q57258549","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356483$AE37F1AB-4BAA-4F49-AE1D-E4168B5F5B44","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0dfbdb0929ddc22bcd5bd1c182b95d3875d4d630","datavalue":{"value":{"entity-type":"item","numeric-id":1164054,"id":"Q1164054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356483$6190F553-7C10-4F06-BCE0-962A6E4DE945","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":"Q1356483$332FC6DB-A291-4D17-825A-CFA87EADBAE1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"841cd3982392b9b8fa5bb217aa031252b8e5d9a9","datavalue":{"value":{"entity-type":"item","numeric-id":5564133,"id":"Q5564133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356483$65EC4354-4EDC-4C23-89F6-82CB4F8EA253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356483$AB77B5E6-B2E3-4C6B-B956-A341E0F11F56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9805d26323ba2d84c83bf1016b34860815554f23","datavalue":{"value":{"entity-type":"item","numeric-id":4017176,"id":"Q4017176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356483$D7BA68F8-C8DB-4D07-B04F-9CB2546365D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67b4ccf441fdba66d0a3b98f8b498783557cced9","datavalue":{"value":{"entity-type":"item","numeric-id":4846495,"id":"Q4846495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356483$9C9A8914-6F31-4D4F-8062-6AF1955E2474","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f5a701a7d31258d2c0eef74cd116458db4c6eee","datavalue":{"value":{"entity-type":"item","numeric-id":3715120,"id":"Q3715120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356483$FDF5AFB4-19DE-44B8-B8C1-0DD8420C1774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c1919d98f9c25de1db9d23bb1c58e3fda970fc7","datavalue":{"value":{"entity-type":"item","numeric-id":4858978,"id":"Q4858978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356483$04FEBFFD-6DDE-4586-8D7F-E555F3145235","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1062162abeca28f558222462b200dacba616efe2","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(96)00247-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1356483$379D8E14-ED5C-4A2C-956D-95F409804D31","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"201b88b3652b1d7ddfb5dd75464c2ab850670078","datavalue":{"value":"W2126105838","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356483$F5777236-4FCD-4E26-9403-5FC3B6699177","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5220f45ed073e5976b12b82be0e51b03e97a3834","datavalue":{"value":{"entity-type":"item","numeric-id":3598776,"id":"Q3598776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d43b575de0a342384f23e6d127e825b87077ed2","datavalue":{"value":{"amount":"+0.91476023","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":"Q1356483$707E15A0-27CF-416F-B0DA-1573AC2BB1F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff0460c07c33842a0b332acd639921df760a3d95","datavalue":{"value":{"entity-type":"item","numeric-id":5487911,"id":"Q5487911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"858ca26412ddeda73186ca1221845399a8e5da40","datavalue":{"value":{"amount":"+0.9114536","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":"Q1356483$08B661A1-C603-4454-8428-D4657D52074B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15c36affb5042fee9085372ccf5710f9ceb5bf37","datavalue":{"value":{"entity-type":"item","numeric-id":5492686,"id":"Q5492686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f51e87ffa8320e45d83cda1ee35cafa9c6f9f565","datavalue":{"value":{"amount":"+0.8980212","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":"Q1356483$C76FF484-EFD5-46B0-858E-C599B66AF2C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3986afc368c0498ee8aa01871b97ea87b5d52512","datavalue":{"value":{"entity-type":"item","numeric-id":5466044,"id":"Q5466044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"446548b7eaf1e1da1a5f5cf6cb03b463936aed42","datavalue":{"value":{"amount":"+0.8937622","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":"Q1356483$4B153498-069C-403A-8BDF-E7F2DB8995ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e67fb139bcff275b813b9952737519d41918e5b3","datavalue":{"value":{"entity-type":"item","numeric-id":1299076,"id":"Q1299076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18509f05805a768344084d30a12dc622d891b9b8","datavalue":{"value":{"amount":"+0.89117455","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":"Q1356483$ED64FD8A-CBCF-45FE-9D9E-3758111AFA1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc09aecbf7304bc44457ed5f9019e0abc8d47900","datavalue":{"value":{"entity-type":"item","numeric-id":4601036,"id":"Q4601036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a7028f0806271d7b84c9d186df48156e17b0faf","datavalue":{"value":{"amount":"+0.8908976","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":"Q1356483$18D322AF-05CA-40A3-BE59-A75E847049E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91a33f044042e8088fee399618ab3ac4b6a75d39","datavalue":{"value":{"entity-type":"item","numeric-id":1024295,"id":"Q1024295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43ad77344bd55bae4c6a1ba5ec4733d6bc4ec6c9","datavalue":{"value":{"amount":"+0.889045","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":"Q1356483$20DF0D32-B070-4F81-8E0A-ABEC6537D748","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa0d6e5743c657be3de9fba760f32bfa63a5ab67","datavalue":{"value":{"entity-type":"item","numeric-id":1292860,"id":"Q1292860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48c95aebe5a46a5a9865f35877903ffbb469e428","datavalue":{"value":{"amount":"+0.88657784","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":"Q1356483$595ECE74-933B-4473-B71D-0F7662EF7D53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c8ae7ec6dff2aea3ac04fea60144bcd2f7a83a8","datavalue":{"value":{"entity-type":"item","numeric-id":1255964,"id":"Q1255964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce423351df3ef1bcb060dda19fd2e5fdfb62641c","datavalue":{"value":{"amount":"+0.8859576","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":"Q1356483$AA9877AE-B566-4A6D-947F-BEA0DDF8D3BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85c8ba0faf9f1b1fe4dfe86d80576f871cee4775","datavalue":{"value":{"entity-type":"item","numeric-id":3439453,"id":"Q3439453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bd567f9044503c3591b5f72c09af3422ba13e43","datavalue":{"value":{"amount":"+0.88448083","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":"Q1356483$10735F2E-D056-4F83-AD1A-EF40ECC2D6F5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1356483","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1356483"}}}}}