{"entities":{"Q1918557":{"pageid":1929299,"ns":120,"title":"Item:Q1918557","lastrevid":71157339,"modified":"2026-04-13T19:51:47Z","type":"item","id":"Q1918557","labels":{"en":{"language":"en","value":"Graphs in which each \\(C_4\\) spans \\(K_4\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 906907"}},"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":"Q1918557$94DDE6CB-E6ED-4B93-937B-1DA6F7A87FE1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e0ce993473fc20189635f970b26311c93199a642","datavalue":{"value":{"text":"Graphs in which each \\(C_4\\) spans \\(K_4\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1918557$C3C78E93-FE6F-40DC-99DF-A354AC1A9F21","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7dff5e9b865d2c7ad804faa83135d22f8d30f9bd","datavalue":{"value":"0854.05061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1918557$63CB57E9-0DD6-4C67-B963-8DCF980B394E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5346984a95f258a04b01f686aaac5b16b4dd7abd","datavalue":{"value":"10.1016/0012-365X(94)00353-K","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1918557$669D680F-7215-413D-8FDF-0E4F65DED5AF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"93a3904bbec182d67e761f38904a81bb2531b67d","datavalue":{"value":{"entity-type":"item","numeric-id":178704,"id":"Q178704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1918557$CA071FC5-2739-430D-BE44-1C4FA5AFA4AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3155ff163c931be8945149a68c11d68da0b397d6","datavalue":{"value":{"entity-type":"item","numeric-id":228779,"id":"Q228779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1918557$BC2A39C9-0881-4525-AE94-FE27AD288EC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb00475fd567190194461a0f087df1793eeae7c4","datavalue":{"value":{"entity-type":"item","numeric-id":6480801,"id":"Q6480801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1918557$2EBF034D-FC9E-452D-A537-DD8BD1368C34","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1918557$5E0BA959-72DE-445F-BC0D-E393801ADCC3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cf43ba359bf7522f1609485030d4b049bb90896f","datavalue":{"value":{"time":"+1997-01-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1918557$0BA1B8ED-BCDE-4785-A044-CC25C9A8B117","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4ae08b5472db3c799f139654089c936bf12f3ead","datavalue":{"value":"This paper concerns a conjecture of the {P.~Erd\u0151s} and \\textit{A.~Hajnal} [Discrete Appl. Math. 25, No. 1/2, 37-52 (1989; Zbl 0715.05052)] that for each graph \\(H\\) there exists a positive constant \\(\\varepsilon= \\varepsilon(H)\\) with the property that every graph \\(G\\) on \\(n\\) vertices that does not contain an induced \\(H\\) has a homogeneous set of at least \\(n\\) vertices. It is known that \\(\\varepsilon= 1/3\\) works for \\(H\\) being the 4-cycle or \\(K_4-e\\). In this paper it is proved that if \\(G\\) contains no induced \\(C_4\\) and \\(K_4-e\\), and \\(n\\geq 6\\), then \\(G\\) contains a homogeneous set of at least \\(\\lceil\\sqrt n\\rceil\\) vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1918557$E3D59991-7424-4232-9535-3CCE08D450B4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1918557$A8C11D7D-4CB4-41B4-A823-3EF500EE3678","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3f28c1be8eb528ed59b00ce14963b41579e0c7f2","datavalue":{"value":"906907","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1918557$DD0562E5-0A9E-40BA-80B2-E110CB84122D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1918557$013E52C7-F925-453B-A608-1F6E67FEB811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6fac036d0386461048e4af513ab5529434c4260","datavalue":{"value":"forbidden induced subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1918557$602C68C9-FF1D-43C8-8AC4-048A2BB579ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e732bfec426ffa0f59d7703db7badf3cf2b9cbaf","datavalue":{"value":"homogeneous set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1918557$9B52FCA0-2D7B-4026-9F98-422003D8B004","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"78229ca0b62b9043e78dddfe0e09bc2dbe34ac8a","datavalue":{"value":{"entity-type":"item","numeric-id":166312,"id":"Q166312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1918557$7D4038A1-411C-43C6-BEE2-9FA85C93E1CA","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":"Q1918557$5CD4268D-25CB-48CA-9B1F-5A3CBA5E8CB7","rank":"normal"}],"P223":[{"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":"Q1918557$E5993E48-9619-43E2-9180-3E7D423EAE52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dea6ee8014164ea0b4ab25365a13b2deaaced58b","datavalue":{"value":{"entity-type":"item","numeric-id":751670,"id":"Q751670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1918557$7F0EABD6-0E19-4EF4-85C7-3C8EF882A79F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"037e5e8f6db333cc058e2aa789858cde90193a45","datavalue":{"value":{"entity-type":"item","numeric-id":5689002,"id":"Q5689002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1918557$4CB6EF8C-0081-474F-AA4B-07956B19B806","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5481763095667beb58073ee207c886ee739c379c","datavalue":{"value":"https://doi.org/10.1016/0012-365x(94)00353-k","type":"string"},"datatype":"url"},"type":"statement","id":"Q1918557$C7E759C9-EBE3-47FE-A1EB-47B1F1E6D6F2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"aa410b6a4793f2d805c99ba95781dc280a876791","datavalue":{"value":"W2034072828","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1918557$C1789C75-AB58-45AF-9105-BB711AB46E71","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49fe0100481e62f6e6c216068b2c67bffe7c7822","datavalue":{"value":{"entity-type":"item","numeric-id":3365464,"id":"Q3365464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3a2f19a8dd16cb8bc0fb47b41d69b8f8601e9bd","datavalue":{"value":{"amount":"+0.9008461","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":"Q1918557$C133A1BA-3210-432D-B067-424E7AD20EE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2da9736995f7e4f9efbd021cf7906938e29b0100","datavalue":{"value":{"entity-type":"item","numeric-id":3615821,"id":"Q3615821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc3cdafe67be8956b364740a6fb0922c86e3cb44","datavalue":{"value":{"amount":"+0.87922025","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":"Q1918557$850D070A-98FE-43BA-A254-88A567102EE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a5533ef0e5298994419ceb018de46b81c20103d","datavalue":{"value":{"entity-type":"item","numeric-id":2997597,"id":"Q2997597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48884bbbe0e57731b45c0303d7cca2f3618a6f64","datavalue":{"value":{"amount":"+0.87621605","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":"Q1918557$020BB4C5-7A2B-4BC3-BB85-70D57334CFB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14365d4ab5e4664598bc3c6c5470ee3f06da1de2","datavalue":{"value":{"entity-type":"item","numeric-id":1262872,"id":"Q1262872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06867daa538ef99ee539735dc9a5e8872a7a8b97","datavalue":{"value":{"amount":"+0.8729197","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":"Q1918557$A85AB958-1BD1-4A60-BA03-B00964967A5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af95aff56865f664d6eb9b631202a81e7784df25","datavalue":{"value":{"entity-type":"item","numeric-id":1926058,"id":"Q1926058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74c7a4ce6bb664b89e98c8dadba65d52bea695b8","datavalue":{"value":{"amount":"+0.8728336","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":"Q1918557$132172D9-23A4-420A-80D2-F41AADB759D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"420f67f546862fde43cc9d703a8793b3a26e9b10","datavalue":{"value":{"entity-type":"item","numeric-id":6096775,"id":"Q6096775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74d1116296eeacb91075ec8ed7f27a170a654b55","datavalue":{"value":{"amount":"+0.8713963","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":"Q1918557$2D9C8F34-E768-4848-8EEE-CD152DAC5D6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abbf5ab59f8199b6c4158a2d658424332a8c9a22","datavalue":{"value":{"entity-type":"item","numeric-id":1336638,"id":"Q1336638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c342fb4bd828c9399bc6a48458a89d12fce08b2","datavalue":{"value":{"amount":"+0.87065965","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":"Q1918557$04A7AC49-E644-4DA6-B93F-E1BBE4532F3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a846dc54fff8856d240589244c3a53eb0e07a5c","datavalue":{"value":{"entity-type":"item","numeric-id":1801686,"id":"Q1801686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04be0a89e3698ae38b305de424e6873b832ef180","datavalue":{"value":{"amount":"+0.87008905","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":"Q1918557$1BE712D3-A962-4B5C-BAE3-299B067E25F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f9558ce8f7c3771fb110df98ee2e068287b3739","datavalue":{"value":{"entity-type":"item","numeric-id":6051050,"id":"Q6051050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1af0b6047afefafdc60ab7807a744445e84a7c95","datavalue":{"value":{"amount":"+0.8697062","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":"Q1918557$DF48BCAF-5446-460A-9D1B-FA1404A22BD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b7cfc4c735779d95ab9f56eaa40c06b580fa6fc","datavalue":{"value":{"entity-type":"item","numeric-id":2804809,"id":"Q2804809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05b79c15edf38b5219060556420bc00758c81512","datavalue":{"value":{"amount":"+0.86810577","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":"Q1918557$079AC727-56D7-46B0-8F6D-E7642574E109","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graphs in which each \\(C 4\\) spans \\(K 4\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graphs_in_which_each_%5C(C_4%5C)_spans_%5C(K_4%5C)"}}}}}