{"entities":{"Q790829":{"pageid":792677,"ns":120,"title":"Item:Q790829","lastrevid":64366191,"modified":"2026-04-11T19:23:03Z","type":"item","id":"Q790829","labels":{"en":{"language":"en","value":"Lower bounds for the clique and the chromatic numbers of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3849257"}},"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":"Q790829$0893E689-93DD-4B6F-BCA2-32741C22C902","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"03cb6d3af135789b6cea07577015c9e93d7fad4a","datavalue":{"value":{"text":"Lower bounds for the clique and the chromatic numbers of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q790829$CF7739F5-271F-4399-A973-14186AD20B2A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aafbc2a93d8dfeef2d9921ea21378d56a2df2f91","datavalue":{"value":"0535.05029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790829$CBCF61DB-C79E-4E5A-9C7B-ACC1055EB20F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"152fa2f823e39e0ae44e19a38dee31e1a5979a97","datavalue":{"value":"10.1016/0166-218X(83)90015-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790829$8258F4DF-C60A-4476-B092-B86BF5604B50","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3896c255b9098440dd8724126c615955891b0434","datavalue":{"value":{"entity-type":"item","numeric-id":790828,"id":"Q790828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790829$1609D9A0-8F7D-4473-9947-8501BC60E597","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0cedb9eedb3adff3d3215a6063ccb67d4489807a","datavalue":{"value":{"entity-type":"item","numeric-id":1820791,"id":"Q1820791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790829$28F92ADC-EDF5-4D3F-9257-12D5F6A6CC8F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790829$5DE121AE-C9DC-473D-9C17-34FBBBBA38AC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q790829$C049DC8C-9A0E-4681-A71B-9CBACC2297EB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"18812ab81c87301fb26ee658bb2802dec639c712","datavalue":{"value":"Because of the difficulty in calculating the chromatic number \\(\\chi\\) (G) and the clique number cl(G), algorithms are generally of the branch and variety. This article presents the history of bounds on these two parameters and makes some valuable improvements. In particular, a bound of Myers and Liu is improved to read \\(cl(G)\\geq n/[n-(2m/n)(1+c^ 2\\!_ v)^{0.5}]\\) where \\(c_ v\\) is the vertex degree coefficient of variation in G. For \\(\\lambda_ 1\\) denoting the largest eigenvalue of G, they find \\(\\chi(G)\\geq n/(n-\\lambda_ 1)\\) and \\(cl(G)>n/(n-\\lambda_ 1)-1/3.\\) Other bounds that are not easily described are developed. They conclude with a constructive lower bound for cl(G) that is always at least as good as the Bondy bound. They tested the effectiveness of the various bounds on random graphs with 20 and 50 vertices. This last mentioned constructive lower bound was usually the largest, suggesting that it is generally the best known bound to date.","type":"string"},"datatype":"string"},"type":"statement","id":"Q790829$FADFA1C3-7DE0-4D09-849B-2C58B79D6500","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790829$685B82C3-7746-4427-A9A0-842F3D1EC255","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790829$E8816AA5-6E56-46AF-999E-8A1409940D88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790829$C8021F0D-FD2B-44CD-BF4E-0D7EEBC0835E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8a09541211712a82529d338fa9f0a678ce315057","datavalue":{"value":"3849257","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790829$71E97457-C727-4C28-835C-E5CCF95AA387","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q790829$A8E7A874-CD3A-42AC-9E17-2E5B00725856","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb2169375ebb26ec0067c3fe2ae2119dcb9b464e","datavalue":{"value":"clique number","type":"string"},"datatype":"string"},"type":"statement","id":"Q790829$AB62C9AB-E300-401C-8E55-5E166C6BB8EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b009faaffc8a8c426743054065b6952bb623f4e","datavalue":{"value":"spectral radius","type":"string"},"datatype":"string"},"type":"statement","id":"Q790829$45E27723-BC7E-4D15-80EC-C6F320EAC8C2","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":"Q790829$A55D3323-FCD5-47D3-BAC8-443297BBE466","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c86b8037f81ff438be9ee7519c7dadf4d3895153","datavalue":{"value":{"entity-type":"item","numeric-id":5572941,"id":"Q5572941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790829$75B0D520-6762-4811-92B7-949D7A0A2041","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55c9c3091aae83b7896276a6a8745b2f13251753","datavalue":{"value":{"entity-type":"item","numeric-id":4129478,"id":"Q4129478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790829$9F37FE11-FF74-48D5-AB26-FE49E4E87262","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f48cfcdee6a83f26e9d742b269ece2559d224dc","datavalue":{"value":{"entity-type":"item","numeric-id":3931003,"id":"Q3931003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790829$EBB169D9-00C4-4D4A-A24B-A11D28E628BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5899e3e12a743d53573a910fcbfa636f0f6c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":3852212,"id":"Q3852212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790829$816875DC-EDC4-47CC-A6D2-E15838EF50E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae74673845da4e2ec58ea2c5bacae070cf1d5538","datavalue":{"value":{"entity-type":"item","numeric-id":5625207,"id":"Q5625207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790829$4F8000B2-D64C-4941-AF4F-499B6714E6E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4dbbe2f3dbd91809e4552f602d5207e47f30d2b0","datavalue":{"value":{"entity-type":"item","numeric-id":5641166,"id":"Q5641166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790829$58454722-DC4C-4964-BFE0-D87ED65F5C3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a705bbf1aef85927902ed3e16efea723fa7dcc1","datavalue":{"value":{"entity-type":"item","numeric-id":4065581,"id":"Q4065581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790829$BA528010-18FB-4D55-97B4-A71C680D8216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8096df8791cf776a33603b62276b064106ad05bc","datavalue":{"value":{"entity-type":"item","numeric-id":3856672,"id":"Q3856672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790829$B8E679B7-0FE6-442C-B7C5-D43654791865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8691ce0ca14717ab9e2af3b5294eb3e0c1171712","datavalue":{"value":{"entity-type":"item","numeric-id":4047574,"id":"Q4047574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790829$9A1E78C2-3855-491A-9347-BE38874024A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1d22e95cfb08114972c1514e26bef4d87d04d8a","datavalue":{"value":{"entity-type":"item","numeric-id":5524918,"id":"Q5524918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790829$39E89DCE-7633-4C2E-8993-90A4D2B80DB6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47adffe299672b3d718d700b54877b50c855a189","datavalue":{"value":{"entity-type":"item","numeric-id":2043671,"id":"Q2043671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb7508885f734bd4bb3a6fff45112c6c2be1277e","datavalue":{"value":{"amount":"+0.8129285573959351","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":"Q790829$4ECB159E-9D23-4542-919F-BB894236A971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"780c4b2e9c019cc1dda1a9c33f41074c605627ea","datavalue":{"value":{"entity-type":"item","numeric-id":1869218,"id":"Q1869218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3873a488bd6492b954e734671a7458762c20af7b","datavalue":{"value":{"amount":"+0.8042067289352417","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":"Q790829$880050EA-6574-4B32-9745-662965C5D28D","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":"1cc6f8572e91e6623898dc0933b37efaee41727e","datavalue":{"value":{"amount":"+0.7983454465866089","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":"Q790829$39E7FC4A-4526-4851-95A5-EEC9ADD7F12B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9164912f48355414bb95934e521e890ed93999ed","datavalue":{"value":{"entity-type":"item","numeric-id":1044204,"id":"Q1044204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75497f6c6d79f9ae0e433871f649984cf5a1f294","datavalue":{"value":{"amount":"+0.7937642335891724","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":"Q790829$BA87A810-D483-4C75-9EC7-CD052EB3D732","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1baf6abe85b52898dd45c59ccb7740d75e425d0e","datavalue":{"value":{"entity-type":"item","numeric-id":2243705,"id":"Q2243705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b3d90907d9204db7cd451ef4ca7f30e0456bc4a","datavalue":{"value":{"amount":"+0.7928323149681091","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":"Q790829$E217D3BE-A379-4DA9-AD45-84E7B5092572","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lower bounds for the clique and the chromatic numbers of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lower_bounds_for_the_clique_and_the_chromatic_numbers_of_a_graph"}}}}}