{"entities":{"Q1068099":{"pageid":1078851,"ns":120,"title":"Item:Q1068099","lastrevid":66665574,"modified":"2026-04-12T11:40:42Z","type":"item","id":"Q1068099","labels":{"en":{"language":"en","value":"On graphs with small subgraphs of large chromatic number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3929031"}},"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":"Q1068099$74DBAD1B-4B65-4B09-A1F5-585B53488477","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c75986d9fd2a5e312512dc6388c1ebd459b6e4f3","datavalue":{"value":{"text":"On graphs with small subgraphs of large chromatic number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1068099$96EB3C5B-B48A-4769-A60F-B49F3D88AB66","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"27c90eb9da32d42646f82b6ea92d599b646da394","datavalue":{"value":"0581.05023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068099$B9879925-9A41-403D-8770-586B77484F17","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6becacdf0dded9d0bac057e287837acb4599ff4e","datavalue":{"value":"10.1007/BF02582932","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068099$C473D7F9-1F11-43C8-B990-56B27007D5AB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c36b77bffff6f43e669d0380d3493f37a56849f","datavalue":{"value":{"entity-type":"item","numeric-id":168591,"id":"Q168591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068099$F654FEA6-CC9E-4CE2-A8B0-26119828B261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0230e1134dc197949da47365171a205c002b5cde","datavalue":{"value":{"entity-type":"item","numeric-id":1068098,"id":"Q1068098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068099$ADD6F41F-4588-42CC-A0F9-DC176AB92AB0","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":"Q1068099$2B4E6861-880D-45A7-9D75-AF7D90B3A01B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1068099$53C79F26-1D5D-48BC-A629-1C7E7DF99385","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"86b6619c6d07d6879ccb2ae9fd461e9a2285562e","datavalue":{"value":"Theorem: For each positive constant c and positive integer k there exist positive integers \\(f_ k(c)\\) and \\(n_ 0\\) such that if \\(G=(V,E)\\) is any graph with \\(| V| =n>n_ 0\\) having the property that \\(\\chi\\) (V,E- F)\\(\\geq k\\) whenever \\(| F| <cn^ 2\\), then there exists a subgraph \\(H=(V^ 1,E^ 1)\\) of G with \\(| V^ 1| \\leq f_ k(c)\\) such that \\(\\chi (H)=k\\). This is a generalization suggested by Erd\u0151s of the following conjecture of Bollob\u00e1s, Erd\u0151s, Simonovits, and Szemer\u00e9di: For each positive constant c there exists a constant g(c) such that if G is any graph which cannot be made 3-chromatic by the omission of \\(cn^ 2\\) edges, then G contains a 4-chromatic subgraph with at most g(c) vertices. The proof is based on the uniform density theorem of \\textit{E. Szemer\u00e9di} [Probl\u00e8mes combinatoires et th\u00e9orie des graphes, Orsay 1976, Colloq. int. CNRS No.260, 399-401 (1978; Zbl 0413.05055)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068099$89EEBB7B-55ED-4D72-8E10-5018D2D3E039","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068099$C651E6C5-3246-4A9A-B3A6-C88AA8ABB7F3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7d9fc2da0ff60403e1ee5f21e2a471b2022b4b59","datavalue":{"value":"3929031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068099$D314602E-F8B9-44DD-A5EF-456FE265F959","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068099$ED1F2F26-4ACA-43B5-A12B-E282BC361555","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e87bb1aed89f5da6ee5d1aa38eb687932a17c03","datavalue":{"value":"subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068099$0ADEE1F4-894A-4098-AD36-7992CBCB4E1D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"79d7d1475cffda86b284945ea46f0b9431d96c99","datavalue":{"value":"Q105583344","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068099$53CF82A1-8C35-4253-A234-C7D8A369F3AB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d3b25dc30b75558579c988a512f98264c780de85","datavalue":{"value":{"entity-type":"item","numeric-id":1171577,"id":"Q1171577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068099$3504AFEF-CAFB-49CC-9C2A-2E14130BC7FE","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":"Q1068099$62A6944B-EB93-459F-977B-EFF9FB133ADD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e4ef4324cd73584d9fd2527788e469b2272b218","datavalue":{"value":{"entity-type":"item","numeric-id":4154888,"id":"Q4154888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068099$D5EC00C1-1873-480F-A82A-9213E175A466","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14d3a78dacd78e15d55715f22ce3c2d625c291db","datavalue":{"value":{"entity-type":"item","numeric-id":289740,"id":"Q289740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63309ae02beb93c0a446fc87c5e07bf6e9ddca6a","datavalue":{"value":{"amount":"+0.95102775","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068099$A14FE5D1-21C7-4A06-8BD3-8086B92027DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64fe968668ea0249b2786843dfba93862ffc6ee7","datavalue":{"value":{"entity-type":"item","numeric-id":2342369,"id":"Q2342369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b0fa1c8bddfa58534f6574663e97e50cf540d1e","datavalue":{"value":{"amount":"+0.9507486","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068099$E92C401F-7920-4902-A50B-4C92E20B1487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ae4653dc932e6c9e4a91266cc7c030485a869d8","datavalue":{"value":{"entity-type":"item","numeric-id":916653,"id":"Q916653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c748f65117688b82d12f1b1f44f0d9db1946538","datavalue":{"value":{"amount":"+0.9279597","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068099$430E86B6-7C0D-4F3D-8660-F5B777D6868F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc3a2abd6481f9f750ed9da75efcb6ba088f3f9e","datavalue":{"value":{"entity-type":"item","numeric-id":3791167,"id":"Q3791167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60e76591f7cc8123363ff12b2a6308d69bfba14c","datavalue":{"value":{"amount":"+0.92794275","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068099$29CB7BB0-CB4F-4DCC-9B99-5C7FC33BE572","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a96b51590cccbe59cf2ba7bd958b7a9ee014f6a","datavalue":{"value":{"entity-type":"item","numeric-id":6133373,"id":"Q6133373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdd1eb0db77c31fc36807615fa2642705d43a3eb","datavalue":{"value":{"amount":"+0.9270989","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068099$479E29B5-C0B8-4859-9686-1797E6FC2D35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f8f92e76ca439de63ab34ece79c1e7077b0018b","datavalue":{"value":{"entity-type":"item","numeric-id":3839717,"id":"Q3839717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3612703ae426fed801405259434a6b953f007536","datavalue":{"value":{"amount":"+0.92631674","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068099$EEC7B9D8-F78B-4640-925A-4FA34CC15850","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47d1dd1979ec27cda3eae7d955718d4f9ff1fe2b","datavalue":{"value":{"entity-type":"item","numeric-id":4351317,"id":"Q4351317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdf65d6cdf91c50fce4f401fe95f93c861fb9a7b","datavalue":{"value":{"amount":"+0.92316735","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068099$DBE01B18-7EE3-42E4-9F98-DD304489820D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e80fd6c11da07a5dc3b6904f8b778a89254621a","datavalue":{"value":{"entity-type":"item","numeric-id":2851500,"id":"Q2851500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a51d772dde77b2da4ff99321a88ff45dd50276fa","datavalue":{"value":{"amount":"+0.91779035","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068099$6AD29324-733D-4918-A07D-10CDF0C374C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"668808adcc51495e37ffc66d6b04cf71a3370488","datavalue":{"value":{"entity-type":"item","numeric-id":4651517,"id":"Q4651517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ced3f55e33f088ead800c2e0982997013f10a08","datavalue":{"value":{"amount":"+0.9163643","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068099$D0F7FFCC-8F64-479D-96FA-62E6836F252F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a530edb54614df04f08449ca7bc662fcf0d03fc","datavalue":{"value":{"entity-type":"item","numeric-id":5058217,"id":"Q5058217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19eb9b5e98e54c1d0d6400e7a684e2fa3c401419","datavalue":{"value":{"amount":"+0.91327906","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068099$E1A814AC-B5EF-4F6F-BC5B-6190A00D979E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On graphs with small subgraphs of large chromatic number","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_graphs_with_small_subgraphs_of_large_chromatic_number"}}}}}