{"entities":{"Q1121277":{"pageid":1132026,"ns":120,"title":"Item:Q1121277","lastrevid":66801957,"modified":"2026-04-12T12:57:48Z","type":"item","id":"Q1121277","labels":{"en":{"language":"en","value":"Inequalities between the domination number and the chromatic number of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4103095"}},"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":"Q1121277$AA7BE54D-D43D-479D-A5E8-154B0FDE24DD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f4ead5f36e08c53fbe0ac7249bf44d38947e8ec6","datavalue":{"value":{"text":"Inequalities between the domination number and the chromatic number of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1121277$50C984C1-C460-4EA4-B40A-D94E9C9629B1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5722b66398b1ca04605dfcb7fd0cfd82ea64bdb4","datavalue":{"value":"0674.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121277$8EC7B775-1E9B-42EF-B82A-7BCF64D0B02E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bc08291ac5bc8788be8151d289033e80bf9ceb35","datavalue":{"value":"10.1016/0012-365X(89)90308-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121277$0C35FD80-9F66-486E-8195-861FF176FF54","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fcc07cfd28b5eedd0ff9795b5630984bf237062f","datavalue":{"value":{"entity-type":"item","numeric-id":1121276,"id":"Q1121276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121277$1F881158-34D0-477B-961F-A775703DA222","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":"Q1121277$BDC07CB2-E912-42E7-92A5-9B5656E8B084","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1121277$721A5B61-534D-4065-90C1-61D45D6A559A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f2d9595c9347da84954648794d64de2a380fd413","datavalue":{"value":"The following inequalities between the domination number \\(\\sigma\\) and the chromatic number \\(\\chi\\) of a (simple) graph on p vertices are proved by a direct application and combination of several old and newer results on these parameters:    For all graphs G it holds \\(\\sigma +\\chi \\leq p+1\\) with equality if and only if \\(G\\cong K_ p.\\)    For all connected graphs G with \\(p\\geq 5\\) it holds \\(\\sigma\\) \\(\\chi\\leq \\frac{p^ 2}{4}\\) with equality if and only if G consists of a \\(K_{p/2}\\) (p even) each of whose vertices is connected with an endvertex.    For all regular graphs with \\(p\\geq 5\\) it holds \\(\\sigma\\) \\(\\chi\\leq \\frac{6}{25}p^ 2\\) with equality if and only if \\(G\\cong C_ 5\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121277$79C33405-8DC0-43A6-99E8-DA5A4BCFC3B5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"fc01f965b0513cf320497fc21a959a6ae364b21d","datavalue":{"value":{"entity-type":"item","numeric-id":427811,"id":"Q427811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121277$F7C59F0F-A45C-4BB0-A881-98F0AFBAF77B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121277$5F79CDFD-1D2C-4CF4-9CAA-107537865ACC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121277$870789A0-DED9-4532-BC36-B4B9C754EEB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ff9d350acea12ffd75e7ed8da6f45c48ff041eef","datavalue":{"value":"05A20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121277$74D54191-A5B3-49A7-8186-C87AFEF176E3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9d5d8ec68bc38386902e3428749d5f1541608228","datavalue":{"value":"4103095","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121277$75C7C98F-2CFC-40A5-8153-D58EF9C7BE80","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10c6d68eec86d7a058a754532f8dbeed17df8712","datavalue":{"value":"finite simple graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121277$3906733E-74FF-479A-BBA6-A1711CDAEDCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1192fcacf464462a2ebf36423b674968a6cbc28","datavalue":{"value":"complementarity relation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121277$0E0D60D9-C5B4-4BFB-B44A-1A3FDB9EDA3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3267d14ab3c644208190b057ee58cacbeb7fa5c7","datavalue":{"value":"domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121277$DA32776C-5D68-4589-B069-ECDC2D47024A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121277$616D014D-4470-4710-9F3F-801CF8735705","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2df313526c4364b4bde459670204713b3745b88e","datavalue":{"value":"connected graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121277$86A31320-E54E-4A36-A6F7-DAECA6595A83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34012c92c499b6a6beb6c6030b4f33ccbf9f4fcc","datavalue":{"value":"regular graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121277$7E3C0CCF-BE4D-4002-A5C4-C4105664A731","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":"Q1121277$BAF56DE1-DCC2-4B5C-91EA-FA3CBEB0C451","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121277$5EE6711A-D1E1-4A4C-8A5A-1461FC6E1430","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":"Q1121277$068FD16B-8F8E-48CA-B1E1-663242C90814","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77cafa6b307b1e0ba183f14f0591d1ad5c4b8d48","datavalue":{"value":{"entity-type":"item","numeric-id":5544082,"id":"Q5544082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121277$F5439B59-E3B2-468A-BEA5-B0924CD3DD83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c121dca7266cc7c3596e352652d4b1cc1a8907c","datavalue":{"value":{"entity-type":"item","numeric-id":5526632,"id":"Q5526632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121277$099233D7-6D90-4A2E-BA49-9C3E523B8813","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45180234b9ea3b2827383abc3f9dc7c73ce4c0b5","datavalue":{"value":{"entity-type":"item","numeric-id":1081617,"id":"Q1081617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121277$99F73AE1-DA36-49B8-B323-932E2FC7C960","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc6c4d7e107786dba55bc9b4ad32e76bdfb58cc6","datavalue":{"value":{"entity-type":"item","numeric-id":3677800,"id":"Q3677800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121277$B6614AED-916D-4911-BB10-91AE2BCDBE83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39955230987edbd9b04725f49e22d86a615e40b4","datavalue":{"value":{"entity-type":"item","numeric-id":3231818,"id":"Q3231818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121277$913EFC0C-E26A-4DF7-AF7E-2602513269BD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ecc94b0c9dd484db9b9d014c2ad513c05749708","datavalue":{"value":{"entity-type":"item","numeric-id":4645587,"id":"Q4645587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c180215ffa014e28d1144e641fed97d7972224c","datavalue":{"value":{"amount":"+0.9598026","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":"Q1121277$6B7167D7-3581-4B9D-83EE-B205D6DBC06F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee4d496f2aa983567744f5b9bb3353060699e7a1","datavalue":{"value":{"entity-type":"item","numeric-id":2462396,"id":"Q2462396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"396fbff7364ad75ef26ccb606bd74d81f709a90b","datavalue":{"value":{"amount":"+0.9333076","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":"Q1121277$153920D1-F3D8-4900-A29F-CE36928B31C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01af332aaf2374a6a08364ae218fa9414f2b1612","datavalue":{"value":{"entity-type":"item","numeric-id":3124135,"id":"Q3124135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee79e53b6d4ace711fa3911ea831df872308452b","datavalue":{"value":{"amount":"+0.9257852","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":"Q1121277$37C8135D-CF73-4EE9-886E-DB62B5C29F77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"332abe30ab0ac947d5339eaea341531c77e76ff4","datavalue":{"value":{"entity-type":"item","numeric-id":3560786,"id":"Q3560786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7bdf6f9326989ccb7bdabb5cc174f17f2d7a20a","datavalue":{"value":{"amount":"+0.92486733","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":"Q1121277$580F96E5-51B2-4BD9-A0A6-0D3A73C43EBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3e56d8fc6a4df961876b5432caa01c4a83de666","datavalue":{"value":{"entity-type":"item","numeric-id":4997222,"id":"Q4997222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d668c0c1eaf60d99a926a6a6f1121e40478e8550","datavalue":{"value":{"amount":"+0.92328167","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":"Q1121277$3153C5A2-AC74-4004-BAD3-A36037BF114A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e65ddf0eec98e9c4b4dcf3dd67d97cf3240a51b","datavalue":{"value":{"entity-type":"item","numeric-id":6073792,"id":"Q6073792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90b93da399ed599607115e467aacebcf11bf11d1","datavalue":{"value":{"amount":"+0.91932523","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":"Q1121277$04B2F1C9-681C-4A78-8C0E-DECB68AC32F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab67e64a33c68871aef98f56e70ffd229f4263d2","datavalue":{"value":{"entity-type":"item","numeric-id":5036674,"id":"Q5036674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f7a37fb3fc2ec9fb890a17d5ab73763dff772ab","datavalue":{"value":{"amount":"+0.91056526","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":"Q1121277$E6EE2DE5-28A1-4D2E-A058-7CBFFD695512","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6bec363fc94ac84bc7201db639933762b6d6d0b","datavalue":{"value":{"entity-type":"item","numeric-id":5069684,"id":"Q5069684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ac106ab870e97b3af0bf838f24482f2bcec3395","datavalue":{"value":{"amount":"+0.9051131","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":"Q1121277$7AA9E0D9-A166-4E8C-8B55-C3D6F30C1F83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"161e01afc27cab1ddfde2de9530e1026a65a21ed","datavalue":{"value":{"entity-type":"item","numeric-id":1421509,"id":"Q1421509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a27ee234f26f232856179eb9c2a86b7157a969b","datavalue":{"value":{"amount":"+0.90085083","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":"Q1121277$DF7CF5B2-2EE4-46A3-AD79-97259CEC6666","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11f50ded5beeb2596fb2e83e625d869caf0063d5","datavalue":{"value":{"entity-type":"item","numeric-id":5572941,"id":"Q5572941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b2c200632ec02989bf08a819106b11ff48f8d33","datavalue":{"value":{"amount":"+0.9006673","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":"Q1121277$4A9C7D88-1583-420E-B1A8-B7C33644B09A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Inequalities between the domination number and the chromatic number of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Inequalities_between_the_domination_number_and_the_chromatic_number_of_a_graph"}}}}}