{"entities":{"Q685554":{"pageid":687403,"ns":120,"title":"Item:Q685554","lastrevid":78195911,"modified":"2026-05-06T11:01:01Z","type":"item","id":"Q685554","labels":{"en":{"language":"en","value":"Some upper bounds for the product of the domination number and the chromatic number of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417438"}},"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":"Q685554$FE386300-06D8-4993-9C71-9BD805B0915D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9340257d5c4bbc176ee45c104ef864d43a23986d","datavalue":{"value":{"text":"Some upper bounds for the product of the domination number and the chromatic number of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685554$40181E92-2758-46DE-8320-130AE464AB8A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5d79ea77ad4e90ec60ab335011a4826af2ff78d4","datavalue":{"value":"0782.05049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685554$1408C456-B6EC-447E-B352-1A04F922552C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"92751c13b58c65c9722a9b753d402f4f39a56eef","datavalue":{"value":"10.1016/0012-365X(93)90074-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685554$7329E36F-BCA2-4116-A8B3-D9DF13067D51","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d6e39983c1ad70f8fb55166da3f8e64fbaf954eb","datavalue":{"value":{"entity-type":"item","numeric-id":685553,"id":"Q685553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685554$B163552E-50A6-49D0-99DD-E9C0C8BB5498","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9b4422e37ea985f640d4cbfe3c8456c60e8e83e9","datavalue":{"value":{"entity-type":"item","numeric-id":186197,"id":"Q186197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685554$0CCC40AE-DD4F-4977-B480-C857F91AA4AC","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":"Q685554$4F91E0B2-03ED-444D-945A-2931BF03086A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"00b02a93155106df3387b19c38bc0ac0db89fb82","datavalue":{"value":{"time":"+1994-01-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685554$14CDE738-1858-4C9F-9DDE-33A1254371F2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0ae3bcdbbacaa71308f899d252ce22c3e046c067","datavalue":{"value":"For a graph \\(G\\), let \\(n\\), \\(\\delta\\), \\(\\gamma\\), \\(\\chi\\) denote the order, the minimum degree, the domination number and the chromatic number of \\(G\\), respectively. Improving results of \\textit{D. Gernert} [Inequalities between domination number and the chromatic number of a graph, Discrete Math. 76, No. 2, 151-153 (1989; Zbl 0674.05030)] and combining several known inequalities the authors prove:   If \\(G\\) is a connected regular graph with \\(n\\geq 6\\), different from the cycle \\(C_ 7\\), then \\(\\gamma\\chi\\leq {(n+1)^ 2\\over 8}\\).   If \\(G\\) is a connected graph with \\(\\delta\\geq 2\\), then \\(\\gamma\\chi\\leq{\\delta\\over 8(\\delta-1)} (n+1)^ 2\\).   If \\(G\\) is a connected graph with \\(\\delta=2\\), then \\(\\gamma\\chi\\leq{2\\over 9} (n+1)^ 2\\).   Examples show that the second resp. third bound is asymptotically best possible if \\(\\delta=3\\) resp. \\(\\delta=2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q685554$138F09FD-2572-4B51-B4AC-3A5772D8C650","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":"Q685554$34828C29-269B-4F42-9C58-3B4A8013DD22","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685554$D3C8941A-EBA6-4976-8A15-603A9D56B05E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685554$EC10E2C8-A945-4D33-8C8A-56B341BEE802","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f9e8fdb246e23cff047198468404facb6a0bde24","datavalue":{"value":"417438","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685554$132B2032-5C36-4E17-A9E5-CEC4779E1062","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b054bbd1ef16f604df0f61144322893e5b9a2a9","datavalue":{"value":"upper bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q685554$0844BB63-5B62-45B6-8F7F-3808E0B0DFB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fae8dc69695ed62681f89d7d9eea2d8a16b8684","datavalue":{"value":"minimum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q685554$32BAF761-48BE-4E27-B82B-97571CAFA719","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3267d14ab3c644208190b057ee58cacbeb7fa5c7","datavalue":{"value":"domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q685554$578DA79D-7436-4219-A8AB-9408ADC77C75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q685554$4E881AC3-434E-4821-95B3-C3ABE98127A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9217cf5fdf9311e03b0d651a5eac92fd9c7100c2","datavalue":{"value":"regular graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q685554$E826457B-0FC7-4847-9760-111B9FD3D7DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b064239038ee1a771c75dcf49f01efada6cdd6a","datavalue":{"value":"connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q685554$124A7B78-520A-43D5-9308-8A8F0EAEEE3D","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":"Q685554$D73E5705-EF40-4FCB-9C0C-5FEE0D0F7E8E","rank":"normal"}],"P223":[{"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":"Q685554$E870FB34-451E-4AE5-8C08-CA080B6586CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5da3b54f7ef8a2117279ae6dffad9f5ec74f16a9","datavalue":{"value":{"entity-type":"item","numeric-id":3818315,"id":"Q3818315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685554$2CEC0C60-A90D-4FDE-B4EF-A546D4843060","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":"Q685554$A6881A4F-4495-47B5-A467-DE7ED3C7DB21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9575347bea448502e8924b42dc15dc79335ac23d","datavalue":{"value":{"entity-type":"item","numeric-id":912870,"id":"Q912870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685554$1977D879-1A59-498A-B4B8-60FD4FB0CC86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85884e874969b1ebb66c422670a156b9789291e1","datavalue":{"value":{"entity-type":"item","numeric-id":1121277,"id":"Q1121277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685554$E31B1C5D-6E60-46D6-99B3-CD1FF3598F2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"402db5507dedffef5c7e618fb72c652f28535d49","datavalue":{"value":{"entity-type":"item","numeric-id":4108373,"id":"Q4108373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685554$0EE9D4EB-5DB9-4458-8807-0BF21AA13752","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a403527d3ce65a104e6d035caf2d719c8f6c0d1","datavalue":{"value":{"entity-type":"item","numeric-id":4552227,"id":"Q4552227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94499cc6ff5c85edfdc666bcd08495eea9da562c","datavalue":{"value":{"amount":"+0.9371650218963624","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":"Q685554$1E48F33C-F866-4830-AE33-D1A5DE201FCA","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":"e5b45571128ba7cc153117cd6839713bba3920bb","datavalue":{"value":{"amount":"+0.8869802951812744","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":"Q685554$F570DE68-203B-438D-9A62-8DBC425A50AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01abac2444a9d657bc98c2d66abaea8fc7306ca0","datavalue":{"value":{"entity-type":"item","numeric-id":1121277,"id":"Q1121277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"532e00295b2b8d52bbc1a1a86ffe4d81d4c9c9c0","datavalue":{"value":{"amount":"+0.8716607689857483","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":"Q685554$585EA647-5DF2-49DB-BC7D-E294C081C1C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b125c4b039900e9d2e91abc16dde09a24508fee3","datavalue":{"value":{"entity-type":"item","numeric-id":4489228,"id":"Q4489228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"feb1210f572163c133b73cfb9e5d2eb6446dc8ea","datavalue":{"value":{"amount":"+0.8210641145706177","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":"Q685554$6D13AEE1-D298-4CAB-BD77-7C14FECF4B29","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":"da1c62daf7e626d2a858e9004a3f98278c865d48","datavalue":{"value":{"amount":"+0.8075433373451233","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":"Q685554$6D3F37A0-D7FC-48AC-B83E-8DA4F5CC1251","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Some upper bounds for the product of the domination number and the chromatic number of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Some_upper_bounds_for_the_product_of_the_domination_number_and_the_chromatic_number_of_a_graph"}}}}}