{"entities":{"Q1306304":{"pageid":1317054,"ns":120,"title":"Item:Q1306304","lastrevid":46849023,"modified":"2025-12-25T17:27:22Z","type":"item","id":"Q1306304","labels":{"en":{"language":"en","value":"Induced cycles and chromatic number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1346956"}},"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":"Q1306304$3B2A9614-3B4D-4A6F-A737-1B0230DD4A4A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6fc20488b5e89d09d57a5171743a1a59a1e4ce3e","datavalue":{"value":{"text":"Induced cycles and chromatic number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1306304$F515979A-B49E-4CC9-AB2A-B8676FF9B755","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"68599154b574fd9bbf18543123b59d0ae8aa2e27","datavalue":{"value":"0936.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306304$D34BDA16-753C-4C25-BD5F-C470F9481A9C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306304$9D95690D-34F0-4951-9E17-AD419612EC1A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4ca1e772005d733ca22cf7d2096deaedd82034ff","datavalue":{"value":{"time":"+1999-12-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1306304$525583C5-429D-4CE2-9DAA-7CD127A06149","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"66fe1ebe1c9a8b13f1f7f27ac7b846eb19d24e28","datavalue":{"value":"The author proves that for any pair of positive integers \\(r\\) and \\(s\\), there exists an integer \\(N(r,s)\\) such that every graph with chromatic number at least \\(N(r,s)\\) contains either the complete graph \\(K_r\\) or an induced odd cycle of length at least 5 or an induced cycle of length at least \\(s\\). This result is a weakened version of two conjectures made by A. Gy\u00e1rf\u00e1s (1985) which are related to the well-known strong perfect graph conjecture as well as the Gy\u00e1rf\u00e1s-Sumner conjecture (1973 and 1981). Several similar/related problems had been studied before by A. Gy\u00e1rf\u00e1s, H. A. Kierstead, S. G. Penrice, D. P. Sumner, E. Szemeredi, W. T. Trotter and Zs. Tuza.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306304$83EC0F2B-FC4A-418F-ACBF-195A6BCC2C6A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306304$92D2DD8C-42BF-4966-99A7-9F755D9DEC4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306304$F11D0676-4308-4C6C-AAC0-AA621B53F919","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"43d4be7079b7e50c937212207402ab8abac56ddc","datavalue":{"value":"1346956","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306304$F27CF3E1-C29A-487B-8528-4835C22DC7A8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306304$D8061B7C-25B5-461E-8E5A-D70A178946B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"94ed6885a1ca21bebabd977bf75106246fc53489","datavalue":{"value":"induced cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306304$B75FC7F3-1344-432E-9F3D-2DC4B72F94DA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f8b2beaa85ff67f6ba8323eb17002460f5e5f0aa","datavalue":{"value":{"entity-type":"item","numeric-id":846045,"id":"Q846045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306304$AA5CBB0F-111C-466D-9544-7A008F9A15AE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0dfbdb0929ddc22bcd5bd1c182b95d3875d4d630","datavalue":{"value":{"entity-type":"item","numeric-id":1164054,"id":"Q1164054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306304$657F45E9-C96E-478C-ABE3-E7A703032E93","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":"Q1306304$622AE553-05DA-42FF-81B3-D627FCC4BAB5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"80dc2459bd2bad28ea1d95f0e4b20284e3314c34","datavalue":{"value":"https://doi.org/10.1006/jctb.1998.1894","type":"string"},"datatype":"url"},"type":"statement","id":"Q1306304$3409ED29-D1F9-41C3-93D1-05F820E02145","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"74dd9b534f60e449ce0e56d21a35ed4b2e5307ea","datavalue":{"value":"W2167467023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306304$4D112FF3-DB1D-4024-A268-3CAA6C15904A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b8b57677a0d06c6630de1f95258ead75ed89053","datavalue":{"value":{"entity-type":"item","numeric-id":4063176,"id":"Q4063176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306304$17FB20B5-DBB7-4302-89B3-728B82804E0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecea865227114740eed2d5859f102d9f3a0ca075","datavalue":{"value":{"entity-type":"item","numeric-id":5749319,"id":"Q5749319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306304$A9F15DEF-CFC9-4065-850E-E828CB2A01C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab1681720f15f93e180f2626e5ed0fb1f9e0ce5e","datavalue":{"value":{"entity-type":"item","numeric-id":1159679,"id":"Q1159679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306304$DD10B68F-71E5-482B-95AE-A8F9C3CE68A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f50bb37b38bae24ae5cc706d9f93c054251453a1","datavalue":{"value":{"entity-type":"item","numeric-id":4284098,"id":"Q4284098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306304$8DEDA980-219F-469A-BE9D-681343C0BFBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"393315370e4506242f35e0350f10b3750ba16551","datavalue":{"value":{"entity-type":"item","numeric-id":4287941,"id":"Q4287941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306304$07FF97BB-E7B4-4DD1-825D-AD02AF488001","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6b9544240625d8906a2d713c69993e1070dc4b0","datavalue":{"value":{"entity-type":"item","numeric-id":1916109,"id":"Q1916109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306304$3CFF2401-32A1-480A-AA95-85C416072B1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3a1992fdcc5452ecb00e89a620b5c678474d2ba","datavalue":{"value":{"entity-type":"item","numeric-id":3129824,"id":"Q3129824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306304$68815597-AFC9-47B6-9B76-68FCE0B8A9BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38a1643a3f55fd10ed31ef36d7cba0e5d3b84f16","datavalue":{"value":{"entity-type":"item","numeric-id":3932997,"id":"Q3932997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306304$59D49EA4-2079-4335-B0D4-DEA4EB075F42","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6ded306668d247e4b01149ea8b4e4b02206688d2","datavalue":{"value":"10.1006/JCTB.1998.1894","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306304$B3D31129-4C94-4C9B-8517-8BB8256F303C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2981722de0ec04f9298aca2d094a6c1015922e4","datavalue":{"value":{"entity-type":"item","numeric-id":1985444,"id":"Q1985444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39d0237b5932590a2addb584b573314c5189e0ba","datavalue":{"value":{"amount":"+0.8283886313438416","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":"Q1306304$A78940EC-4B52-4947-A56D-568CE34F48DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb56b9eec5a9d39395f9c3d12c3505de393a09c0","datavalue":{"value":{"entity-type":"item","numeric-id":1693168,"id":"Q1693168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1bc201d8f28730b1842a4ececfbccc7f143537b","datavalue":{"value":{"amount":"+0.8266763687133789","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":"Q1306304$4E8E236F-3EBC-44DF-849B-1DB1533FDE25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbfb10db1ffcf278c67c314deaebbe73040b865e","datavalue":{"value":{"entity-type":"item","numeric-id":256991,"id":"Q256991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b33263d50e7f168e6fddf26d868606cdf63e587","datavalue":{"value":{"amount":"+0.8262749910354614","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":"Q1306304$41C133DF-E718-4492-94FE-7A468B3D1A16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8acebb7e00ce738cd41668eb00dfe30daf789147","datavalue":{"value":{"entity-type":"item","numeric-id":326809,"id":"Q326809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a07b3aa14130d00b276fc7c64484d3f20ba3c257","datavalue":{"value":{"amount":"+0.8243028521537781","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":"Q1306304$0D0E915A-623D-494D-B4BA-C2A2F93A078B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e650165c34558716d5fdaaf60eaa443df0c49abf","datavalue":{"value":{"entity-type":"item","numeric-id":2284726,"id":"Q2284726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6e1efc2da44363515a443134cd698cac947d40b","datavalue":{"value":{"amount":"+0.8209642767906189","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":"Q1306304$FC5E03D2-1DEA-4621-BCDB-5330C5272142","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1306304","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1306304"}}}}}