{"entities":{"Q1313348":{"pageid":1324098,"ns":120,"title":"Item:Q1313348","lastrevid":67147401,"modified":"2026-04-12T15:36:50Z","type":"item","id":"Q1313348","labels":{"en":{"language":"en","value":"On graphs \\(G\\) for which all large trees are \\(G\\)-good"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 490737"}},"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":"Q1313348$4955B216-D887-4DD2-BD41-4ED9ECE2C403","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"76aa5eb413b6ba2740ae53c4dd0a7c8e124ee57d","datavalue":{"value":{"text":"On graphs \\(G\\) for which all large trees are \\(G\\)-good","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1313348$D5FD1602-CEB3-4EFB-A53D-ACE10E4C008F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"251d07571516393f2c273e03ac7c23ae22a74572","datavalue":{"value":"0788.05069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313348$1B0BAC12-77DE-45DB-9920-E47B281778ED","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"54522bf2626ef3d50aade77a46d6a74555f28fdb","datavalue":{"value":"10.1007/BF02988318","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313348$548AFC59-E737-4B4D-A53F-89AE5A427837","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce4aee54645fb34a947a8e72345e94b43fefa3e4","datavalue":{"value":{"entity-type":"item","numeric-id":801934,"id":"Q801934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313348$B65B4C5A-2E23-4CE3-AC69-2A7BB47721EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a90237f4fbe17f8aa89942b7417b8396bf1098f7","datavalue":{"value":{"entity-type":"item","numeric-id":175582,"id":"Q175582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313348$B8D3E18B-66F2-4E84-AB59-823E67C43665","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":"Q1313348$12BF6163-E41E-47EE-8FBC-1E2ADBB59FF7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"531f9d9920ed2df4b2aa83821def238584cfd8b0","datavalue":{"value":{"time":"+1994-05-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1313348$5747180F-3A3B-44C0-A300-47DEC6AA93A5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"981763754f71737e525379ac57756f9e83ced822","datavalue":{"value":"If \\(G\\) is a graph with chromatic number \\(k\\), then the `chromatic surplus' of \\(G\\) is the largest number \\(s\\) such that every proper \\(k\\)-coloring of \\(G\\)'s vertices admits, for each of the \\(k\\) colors, \\(s\\) vertices of that color. In the previous paper [J. Lond. Math. Soc., II. Ser. 24, 405-413 (1981; Zbl 0474.05051)] the first author proved that if \\(G\\) is a graph with chromatic number \\(k\\) and surplus \\(s\\), and if \\(H\\) is a connected graph on \\(n\\) vertices, where \\(n\\geq s\\), then the generalized Ramsey number \\(r(G,H)\\) satisfies \\(r(G,H) \\geq (k-1)(n-1)+s\\).   In this paper, the case \\(s=1\\) is examined closely. It is proven that there are two sets of multipartite graphs \\(L(k,m)\\) and \\(M(k,m)\\), \\(k= 1,2,\\dots\\) and \\(m=1,2,\\dots\\), such that the following are equivalent for each graph \\(G\\):   I. The chromatic number of \\(G\\) is \\(k\\) and for some \\(m\\), \\(G\\) is a subgraph of both \\(L(k,m)\\) and \\(M(k,m)\\).   II. For sufficiently large \\(n\\), every \\(n\\)-vertex tree \\(H\\) satisfies \\(r(G,H)=(k-1)(n-1)+1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1313348$E7924FEB-2D21-46FD-81F5-495289BE0643","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313348$C55A8F52-B1A1-4344-9911-E8164128E493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313348$401529C3-60C3-46DC-8102-AF028097AED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313348$2CD9EC5D-610A-4679-AE39-50B4633A34DD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d1e79ad829eccd4dce9dfa9c5525e3973385c44b","datavalue":{"value":"490737","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313348$64BCD492-CF80-43E7-8F72-D28BC934CA33","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1313348$78B852DB-4DB1-4740-945D-B5A77AA20472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4782e6f077c3c4bba48f18176be4e8f73249ace5","datavalue":{"value":"colors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1313348$41D33291-5F35-449D-9314-BB8551F074C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b7fe948a02583ea1335bba83f0b7de214b3c8dcf","datavalue":{"value":"surplus","type":"string"},"datatype":"string"},"type":"statement","id":"Q1313348$B23145C1-A2A6-4085-B5CA-24DEA483C616","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9fb479b004c9708e2a1736d335a18ddd8c23d9f","datavalue":{"value":"generalized Ramsey number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1313348$28D00049-B757-4BA1-8E2D-E180A6E61BE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1313348$33C4964B-8378-43ED-9A9D-3F4BB865E96F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f4c2e453a383fe1e064f27e4ca3ff49f8a1646b9","datavalue":{"value":{"entity-type":"item","numeric-id":587174,"id":"Q587174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313348$DCCE41EB-0897-40FF-A746-4A8B93B5F3DF","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":"Q1313348$BFCE4F4A-2404-434C-8B15-76F47B03642B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a69a74fa77e8f8db84efeb235a3de1780b9c1c76","datavalue":{"value":{"entity-type":"item","numeric-id":3929770,"id":"Q3929770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313348$ACD34D7E-0739-4F62-B46A-D1012F6AD47F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a2f2c41d77cdd8d4d4ddbc04ae6036ecd5c4037","datavalue":{"value":{"entity-type":"item","numeric-id":3795689,"id":"Q3795689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313348$0601D9BA-F219-484D-814F-77DF6817D5D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a840cb7076407713eb9ec4da13f1165c36c3ed7","datavalue":{"value":{"entity-type":"item","numeric-id":3331251,"id":"Q3331251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313348$0A7F4747-3B7F-4298-B0CD-18104B45AFDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0943dc25cfcec69e0637fd7acdbb0419162b6667","datavalue":{"value":{"entity-type":"item","numeric-id":1087890,"id":"Q1087890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313348$BE85A6B1-4C5D-4EF3-9424-B38804F9ED9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e089490a868776d981fd4a1ecf627c0f26f43446","datavalue":{"value":{"entity-type":"item","numeric-id":4120601,"id":"Q4120601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313348$658645FF-861E-4C95-AD43-A78383B7D927","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d39eef109a70e512dce612b5c2a899d86a3aedd","datavalue":{"value":{"entity-type":"item","numeric-id":2549332,"id":"Q2549332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313348$981473AB-0434-461A-97F7-19B019CEB87D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12e2f0ae4e5f5b786acd7496b339013812095113","datavalue":{"value":{"entity-type":"item","numeric-id":1076043,"id":"Q1076043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313348$83D1C7C5-C5B3-4770-B258-6178F7B030E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddb209b5f842758c420a337fc7ccf411f373b50b","datavalue":{"value":{"entity-type":"item","numeric-id":2526108,"id":"Q2526108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313348$EB42B838-8AF8-4BE5-81AA-875ECA1AFC46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4534d792f5262a1f297a74f9b43efedcc5cd94ec","datavalue":{"value":{"entity-type":"item","numeric-id":4760022,"id":"Q4760022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313348$025A45AC-7517-4DCD-9805-9BA23426614B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2c594e9705e780a6a4b2b01479e5d5553e79570","datavalue":{"value":{"entity-type":"item","numeric-id":5572939,"id":"Q5572939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313348$0B89C91E-9B25-4B19-B81C-2E009F1D9966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"887ce430b000ffd8813e06446b140ace91a67a26","datavalue":{"value":{"entity-type":"item","numeric-id":5548826,"id":"Q5548826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313348$D7141F92-DB2A-4709-95B7-A8BEB03648D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c1bb97e5aa8cede73a154b925bb1362eeb78ef7","datavalue":{"value":{"entity-type":"item","numeric-id":5558479,"id":"Q5558479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313348$71A7F2FB-286A-42CA-8576-8792D1BE7F96","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a422f5e10fe0b6e664ac908d558f3b02c00b8d0a","datavalue":{"value":{"entity-type":"item","numeric-id":1087890,"id":"Q1087890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe45d152878e18487262fb148023aee878fa16e2","datavalue":{"value":{"amount":"+0.9046227335929872","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":"Q1313348$CDA2D30A-6E89-4A98-A2F4-9CCF02399A4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f8a4a1c6ee00a7da4e5a1339d7b3e0250eff164","datavalue":{"value":{"entity-type":"item","numeric-id":6041579,"id":"Q6041579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09eedbf858def5e519b1b9849480ba9c727f5dcd","datavalue":{"value":{"amount":"+0.8825341463088989","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":"Q1313348$89A1B3D9-12E4-439C-B060-93B1D0E5B1AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccfb6c1d14adcbfc283ac064b8c4b9133981b47a","datavalue":{"value":{"entity-type":"item","numeric-id":4294586,"id":"Q4294586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d3e4bcfdddc81fdb77e1c10a85ba1dd51593582","datavalue":{"value":{"amount":"+0.8787237405776978","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":"Q1313348$C4C3CB3A-FD17-4489-B94C-56490FCE4054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f963dd952b375ec7ceb4d91b5604cf30b7edb5f","datavalue":{"value":{"entity-type":"item","numeric-id":3976614,"id":"Q3976614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0439a23a8ee2cfdace8449cad0f17b603091a01","datavalue":{"value":{"amount":"+0.8778015375137329","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":"Q1313348$4C81D980-000E-410F-86DE-3514B61D20E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5dec09eaa38bf5a5004d9a8f5bc1cabe0eafb21","datavalue":{"value":{"entity-type":"item","numeric-id":5858874,"id":"Q5858874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f9c98e93115229ebce05726113aa4af0a5a1c39","datavalue":{"value":{"amount":"+0.8557112216949463","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":"Q1313348$2ED8C8DE-74BF-4355-B9B4-794808485A02","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On graphs \\(G\\) for which all large trees are \\(G\\)-good","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_graphs_%5C(G%5C)_for_which_all_large_trees_are_%5C(G%5C)-good"}}}}}