{"entities":{"Q916670":{"pageid":918518,"ns":120,"title":"Item:Q916670","lastrevid":49395151,"modified":"2026-01-07T02:18:43Z","type":"item","id":"Q916670","labels":{"en":{"language":"en","value":"Contractions and minimal k-colorability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4154466"}},"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":"Q916670$35C98455-266F-4840-80DF-BAD7ABD89D8D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5e09e386f4c71f58d7cab41b99e030b0d68b1ee1","datavalue":{"value":{"text":"Contractions and minimal k-colorability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q916670$3AE471A6-FB75-492E-A2DE-7D5039605B8C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d788056e1b900d45a084e196600aba8fb9493e3f","datavalue":{"value":"0704.05017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916670$836FE450-F6CD-465B-A498-17F50645A22E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3606fc9743be98ee65a3ba93f11bf7df13da8585","datavalue":{"value":"10.1007/BF01787480","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916670$45D5549E-F015-4CC8-9E6D-B2063FC932E1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"17fcd7139afa5567c823530fba22122acb06092a","datavalue":{"value":{"entity-type":"item","numeric-id":175498,"id":"Q175498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916670$627BD3E7-7AB5-4AEF-8C6A-2607EC225D76","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":"Q916670$5DE5FD23-ACF5-44A2-806B-E6D532157B7B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q916670$59C06C19-EA4F-488A-948E-96002B132BE6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ff9a4dd7fda28df49cc6d83fd974c5a6ca6c80f0","datavalue":{"value":"Coloring the vertex set of a graph G with positive integers we can define the chromatic sum \\(\\Sigma\\) (G) of G. It is the minimum sum of colors on all vertices of G. The strength of G is the largest integer that occurs as color in every coloring whose total sum is equal \\(\\Sigma\\) (G).    The main results are given by the following theorems: Theorem 1. Every tree of strength s has at least \\(t(s)=((2+\\sqrt{2})^{s-1}-(2- \\sqrt{2})^{s-1})/\\sqrt{2}\\) vertices. Moreover, for every \\(s\\geq 2\\) this lower bound is sharp and the smallest tree \\(T_ s\\) is unique. Theorem 2. For every natural number \\(s\\geq 3\\), there are two trees \\(T_ s\\) and \\(R_ s\\) of strength s, such that every tree of strength at least s is contractible to \\(T_ s\\) or \\(R_ s.\\)    The trees \\(T_ s\\) and \\(R_ s\\) from theorems 1 and 2 are rooted trees described recursively. E.g. \\(R_ s(s>1)\\) we obtain from s copies of \\(R_ 1\\), s-1 copies of \\(R_ 2,...,2\\) copies of \\(R_{s-1}\\) by joining their roots with a new additional vertex (the root of \\(R_ s)\\). The tree \\(R_ 1\\) is just one vertex. Some open problems are given in the concluding remarks.","type":"string"},"datatype":"string"},"type":"statement","id":"Q916670$497134AF-B62B-44FC-98C5-E30A6CE487E5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ebe4d44a08a58073803722e37fc039de15c45af0","datavalue":{"value":{"entity-type":"item","numeric-id":761465,"id":"Q761465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916670$F75BDE20-4A6C-401B-B896-4E2C7233ECDE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916670$343ADF99-176C-4901-8C01-6B51E4E48E88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916670$A9F930A1-CA87-4824-91E0-C52DA579E91A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916670$1E8A549A-6982-4657-9D0A-76F0FAE55AE0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d44ec0c6fc16a98f6087798fe80cc9c9d3a5c508","datavalue":{"value":"4154466","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916670$68EC15F9-7625-4900-BB37-789CA7A796E6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c436ec2c65457defc412ebdc01dc33c47674be5","datavalue":{"value":"minimal coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q916670$9733FFCA-8D09-4DCE-8064-A4045289C777","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4605262f950382e87dc58df46038532164191769","datavalue":{"value":"contraction","type":"string"},"datatype":"string"},"type":"statement","id":"Q916670$41E51F27-CCA8-4D86-9A7D-AC6415DCE4BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15b66a6079b846629b0c8e49fc4dd12461f6a73e","datavalue":{"value":"chromatic sum","type":"string"},"datatype":"string"},"type":"statement","id":"Q916670$90C50AD3-CAD0-42A3-9084-144B429E4FBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f8a1391448f889e85bcb226231a6e64538865dc3","datavalue":{"value":"strength","type":"string"},"datatype":"string"},"type":"statement","id":"Q916670$F28DB796-59A9-40BD-AD41-EAB858757A81","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":"Q916670$A6F9AD59-3662-4453-A579-BFC5440C5539","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3f92d2022f67774e7fccd1cd2348a499d5bfbd5","datavalue":{"value":{"entity-type":"item","numeric-id":4830805,"id":"Q4830805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916670$228BBD82-C055-4AFE-AD50-D0089D0A7D9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e83270fa3e07f4791bc07cffb7f823711cb875f1","datavalue":{"value":{"entity-type":"item","numeric-id":3832591,"id":"Q3832591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916670$2CA60389-958E-4AB8-B68F-4870008BAE77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d7d2ee5bc9d85fd588eeccacc8ae1bc1099ce15","datavalue":{"value":{"entity-type":"item","numeric-id":3990593,"id":"Q3990593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916670$8681FBE9-EFD5-42CA-9FC4-0F5FA411BFF0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e22c0323f7fd454fd68b8594d2e2994df84b59a5","datavalue":{"value":{"entity-type":"item","numeric-id":4719325,"id":"Q4719325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9288f02d03c16683f01b5d0d07daa6b15228550c","datavalue":{"value":{"amount":"+0.9103750586509703","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":"Q916670$137D1305-2AA8-4621-AD36-A96D3D3DB8A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b6d002c316cebf51433242ba1cb936afe7aba38","datavalue":{"value":{"entity-type":"item","numeric-id":967294,"id":"Q967294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9288f02d03c16683f01b5d0d07daa6b15228550c","datavalue":{"value":{"amount":"+0.9103750586509703","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":"Q916670$F7630A2B-EB7F-4C39-A2E5-0B4FF427B912","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28a95348c9ee0964c12017bd4dfbc6b97207fefa","datavalue":{"value":{"entity-type":"item","numeric-id":1974540,"id":"Q1974540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af7444e0a5cf62f123986ada1877e5babb0d56ec","datavalue":{"value":{"amount":"+0.8173556327819824","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":"Q916670$6FB700FE-7832-4520-B1D2-17049D344CDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22e97449f0ce5b0e3d90d82a64108000e03af194","datavalue":{"value":{"entity-type":"item","numeric-id":3483299,"id":"Q3483299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a1148f407ff80aba58afdd92ecd9b12c9c05370","datavalue":{"value":{"amount":"+0.8150395154953003","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":"Q916670$D0C2E664-2D0F-4E24-A752-62029015EA31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b4e83a88e825f785f724c39089bdc58a491d3f7","datavalue":{"value":{"entity-type":"item","numeric-id":3503528,"id":"Q3503528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9943c6beed54f36cc1ac2d610f2793189883c1f","datavalue":{"value":{"amount":"+0.8144179582595825","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":"Q916670$E840C66B-1CC2-4381-A28B-8C44FB187232","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:916670","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:916670"}}}}}