{"entities":{"Q1340118":{"pageid":1350857,"ns":120,"title":"Item:Q1340118","lastrevid":70184970,"modified":"2026-04-13T13:01:32Z","type":"item","id":"Q1340118","labels":{"en":{"language":"en","value":"Size, chromatic number, and connectivity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 700934"}},"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":"Q1340118$0E59A323-A109-408E-B596-72A6DF88CBB4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2350e391424c94b343901a63b46e489022888662","datavalue":{"value":{"text":"Size, chromatic number, and connectivity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1340118$C64A3513-83F9-4F9A-B369-1AE8F496FD3E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ab90d959a25f3e6c92cb043d324ccd18360312a5","datavalue":{"value":"0817.05026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340118$72841B61-312E-4CAA-86DF-DD0358573861","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a81a3639e06a49236db788ecd8f66f69fb2900e5","datavalue":{"value":"10.1007/BF02986667","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340118$5A3F95DC-EAAE-4210-9EC0-BE85BAA6BD73","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"102731665f1abbef444af7c07327102ab7e9ee7b","datavalue":{"value":{"entity-type":"item","numeric-id":807636,"id":"Q807636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340118$D18E1A29-B668-4BC9-88DC-7A8F9F1C8716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4d4c73f0a1fcfa77f8c56f84fd9c0566fb0d581","datavalue":{"value":{"entity-type":"item","numeric-id":185079,"id":"Q185079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340118$DD5BBF9E-549B-4F0A-A787-AC101E9F0045","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"680babdb522ef7e0908282a13a4b4c247d62cb7e","datavalue":{"value":{"entity-type":"item","numeric-id":1097703,"id":"Q1097703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340118$56380128-BA94-4B69-91E9-2F17EE06B93F","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":"Q1340118$42FDF56B-DE85-44F3-873F-1D200FC998B8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"19216b5631ab2959a22cb1886f3fbbc3003fecf5","datavalue":{"value":{"time":"+1995-08-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1340118$FC957C0B-3E83-49FC-BA9B-42131B4D4CB8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d1fb0986003b1afe75dc7ba0cea9e346fdbdee1b","datavalue":{"value":"Let \\(g(n,k,c)\\) denote the minimum number of edges in a \\(k\\)-edge-connected graph having order \\(n\\) and chromatic number at least \\(c\\) (\\(n> k\\), \\(n\\geq c\\)). A graph is vertex -- \\(c\\)-critical if \\(\\chi(G)= c\\) and \\(\\chi(G- v)= c-1\\) for every \\(v\\in V(G)\\); \\(G\\) is \\(c\\)-critical if it is vertex -- \\(c\\)- critical and also \\(\\chi(G- e)= c-1\\) for every \\(e\\in E(G)\\). Theorem 1. Every connected \\(c\\)-chromatic \\(n\\)-vertex graph has at least \\((\\begin{smallmatrix} c\\\\ 2\\end{smallmatrix})+ n- c\\) edges, and this is best possible. Theorem 2. If \\(n> c> k\\geq 3\\), then \\(g(n, k,c)\\geq (\\begin{smallmatrix} c\\\\ 2\\end{smallmatrix})+ \\lceil\\frac{(n+ 1-c)}2\\rceil\\), except \\(g(n,k,c)= (\\begin{smallmatrix} c\\\\ 2\\end{smallmatrix})+ \\frac{(n+1- c)} 2-1\\) if \\(c= k+1\\), and there is a \\(c\\)-critical \\(n\\)-vertex graph with \\(\\frac{(c- 1)(n+1)} 2- 1\\) edges. Theorem 3. If \\(n\\geq c+k\\) and \\(c\\geq k\\geq 2\\), then \\(g(n,k, c)\\leq (\\begin{smallmatrix} c\\\\ 2\\end{smallmatrix})+ \\lceil \\frac{k(n+ 1- c)}2\\rceil\\). Theorem 4. If \\(c\\leq \\lceil\\frac{k+ 1}2\\rceil\\), or if \\(c\\leq k\\) and \\(n> k+ c\\), then \\(g(n,k,c)= \\lceil\\frac{kn} 2\\rceil\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1340118$CE2FD6FA-2877-4628-A86C-F5D7871BFC9C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340118$369842A7-8835-4B00-AC8E-0E6E98E6F45B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340118$0826B340-2474-4976-9BC8-E4CB65B57A0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340118$9680F455-E499-413A-81A2-C32D1EC8DDF6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f74275040832f79989867870dfbdfa47fb549b65","datavalue":{"value":"700934","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340118$A021FF83-AF82-4F39-8381-6F9E9A79B4E9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41bdc3b6724c41e6d12d51cd77ef843e77f7dd10","datavalue":{"value":"size","type":"string"},"datatype":"string"},"type":"statement","id":"Q1340118$E5E295A8-CAB4-4D5B-A50C-8272EBB8477F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1340118$BF8541AC-9E22-4030-91A0-A08E82EF1D2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1340118$E788F80D-613F-4CEC-913E-987F690914D7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7d410aa128a8b8a63913c9594604f4ec3d0ad8b4","datavalue":{"value":{"entity-type":"item","numeric-id":590664,"id":"Q590664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340118$79FD26ED-20A6-44B6-AA61-1765C1D3A0F7","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":"Q1340118$E8FAF3B8-A6C3-4ABD-A865-8C87D4C37F06","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340118$04731342-2724-47F7-8DFB-31C9321ACCD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24740898104d4c73d726dfe5ed5c3a2648f291b3","datavalue":{"value":{"entity-type":"item","numeric-id":5821654,"id":"Q5821654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340118$1001A443-E96E-4060-8ECC-D4D37A0BAF43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b5a77f691c73d3cc84a775a0deb455c68b0dbbc","datavalue":{"value":{"entity-type":"item","numeric-id":3241662,"id":"Q3241662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340118$BC3072C2-3825-49B1-B0AD-D8F1567A95DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02c160b73834e9fd25d1d5c33f3764e4deb50849","datavalue":{"value":{"entity-type":"item","numeric-id":4052158,"id":"Q4052158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340118$AF25FDCD-60B2-4D52-9BE2-51774B6E0961","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e3ceeaa0ced2d49d09433dcaa8913ae6f36ddf6","datavalue":{"value":{"entity-type":"item","numeric-id":5724439,"id":"Q5724439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340118$AFA85C91-31C4-4EE3-8BE7-63B5BE6D7BFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2496b94bc65e4a7934713ce25c43ce4e46a57fc6","datavalue":{"value":{"entity-type":"item","numeric-id":5613119,"id":"Q5613119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1340118$6D87B7AE-7E4F-4311-B4D2-8A719CDEA834","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"20b7e17d217011d7762833d99a7275547fade566","datavalue":{"value":"https://doi.org/10.1007/bf02986667","type":"string"},"datatype":"url"},"type":"statement","id":"Q1340118$0285624E-680E-48B5-814F-69672EA81F0D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6cff5fe79f80a44ffda0b56ffaf0022e68a2e8e9","datavalue":{"value":"W1968076455","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1340118$32C3EE85-5766-4D8A-9F40-21C9CF8BE043","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"115f5719e926552e57751a01b442f89720da9968","datavalue":{"value":{"entity-type":"item","numeric-id":4301672,"id":"Q4301672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"964742a071fd1158fdf09ed1aa857d189815029f","datavalue":{"value":{"amount":"+0.8482876420021057","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":"Q1340118$EBA83760-C4C5-4259-B4DB-14AFF5AE14B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ccc9f5a7d07f9cf270568bdb985652d339bcf86","datavalue":{"value":{"entity-type":"item","numeric-id":4697572,"id":"Q4697572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b92b5a7d7bc8ac17e4cf261d6c19c6ecf293c49c","datavalue":{"value":{"amount":"+0.8218042254447937","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":"Q1340118$2810D8B5-A374-4B81-8679-689CE5C0E7FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b288ccbf79987b16b48a7ae3d2fa2ebf1de28d0f","datavalue":{"value":{"entity-type":"item","numeric-id":1584424,"id":"Q1584424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8984d12d3043d1d84d9d9a223f93853f93fe1802","datavalue":{"value":{"amount":"+0.8095935583114624","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":"Q1340118$D1A479D6-33D0-4E65-BB89-1F8C57E542A1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Size, chromatic number, and connectivity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Size,_chromatic_number,_and_connectivity"}}}}}