{"entities":{"Q2363116":{"pageid":2373859,"ns":120,"title":"Item:Q2363116","lastrevid":72600288,"modified":"2026-04-14T06:00:14Z","type":"item","id":"Q2363116","labels":{"en":{"language":"en","value":"Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6744570"}},"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":"Q2363116$BB816BB8-F27D-4FF2-89C2-A6C671DF481A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"28b701ee80769866f0f2dd19a96b1832f47ad2fd","datavalue":{"value":{"text":"Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2363116$CC8BFD43-71AA-43E4-BFDF-85B1B0436C88","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e7078f10fb371a98f13e3dfbf83117d7b8f90adc","datavalue":{"value":"1366.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363116$316B7F5E-B2CD-477B-A600-9754969595C2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363116$C9C30250-430C-4D93-97FC-932C21BCD478","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"757d56442149c8e74ad624bf696390baa904ca56","datavalue":{"value":{"time":"+2017-07-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":"Q2363116$5CA333B2-8BE9-4D00-AEDC-778BA18A23ED","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bbbba3c46dde90151d48a74339c3a5f50121fb65","datavalue":{"value":"https://arxiv.org/abs/1702.01094","type":"string"},"datatype":"url"},"type":"statement","id":"Q2363116$2BCACCDC-AA0F-4AAB-BEEF-D0AB99A786E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"54c6f1f50c92362590b0ebc6aa986a64857cfbb4","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p53","type":"string"},"datatype":"url"},"type":"statement","id":"Q2363116$86800C0A-2C3F-4D44-98CD-C39C5A22BFE8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"41ac026da498ce5912d2922d5cfff8b4a0ea7a0e","datavalue":{"value":"Summary: We prove that for all integers \\(\\kappa, s\\geq 0\\) there exists \\(c\\) with the following property. Let \\(G\\) be a graph with clique number at most \\(\\kappa\\) and chromatic number more than \\(c\\). Then for every vertex-colouring (not necessarily optimal) of \\(G\\), some induced subgraph of \\(G\\) is an \\(s\\)-vertex path, and all its vertices have different colours. This extends a recent result of \\textit{A. Gy\u00e1rf\u00e1s} and \\textit{G. S\u00e1rk\u00f6zy} [Electron. J. Comb. 23, No. 4, Research Paper P4.46, 5 p. (2016)] who proved the same for graphs \\(G\\) with \\(\\kappa=2\\) and girth at least five.    For Part II see [\\textit{M. Chudnovsky} et al., J. Comb. Theory, Ser. B 118, 109--128 (2016; Zbl 1332.05053)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2363116$30F2F8F7-1122-454C-8A52-910D04269B55","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363116$8B73802C-ECE8-4904-A939-9101A8D150C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363116$796B4226-FFF9-4464-A33E-48FBB7F7EF85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363116$20EFC80B-FF53-43DD-8B13-B32B888D54EB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"606cd3f11ab047cb361aebb49880ab4c52285415","datavalue":{"value":"6744570","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363116$DD5BF2E6-40C5-4155-BEF4-90D3FD3A11D3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59e104fc9083dc8c4e491b340ba5128d82bfc9b1","datavalue":{"value":"colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2363116$F7A2E615-644B-4C69-A55F-EB8C133724E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e773712b5ff57776d2c3aef1a5720c4bd89bdedc","datavalue":{"value":"rainbow","type":"string"},"datatype":"string"},"type":"statement","id":"Q2363116$9D024627-BFC4-4863-9BB1-878FFCFC2A15","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":"Q2363116$005EF502-516C-47A3-966E-48110D6EDA11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b7666b1aea36d852e5d73efdf8f9faa64e3f54f","datavalue":{"value":{"entity-type":"item","numeric-id":705887,"id":"Q705887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363116$70851E24-5E31-41BB-974A-27F9C977B61B","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":"Q2363116$071DF8D3-FF2F-41AC-99DD-E604B387E882","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"678a260dcb14adb27a93446b1b14573456bc7eaf","datavalue":{"value":{"entity-type":"item","numeric-id":1633601,"id":"Q1633601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363116$656C053C-9B29-4168-AF23-789231618304","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bdd250a45275500c245c98aa669a4cad3fe76cd","datavalue":{"value":{"entity-type":"item","numeric-id":5545303,"id":"Q5545303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363116$7A7F05EC-1C10-4487-824F-58E77904E52B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6de6f36eb025a6c05ae4c9d474774c3991c46cb2","datavalue":{"value":{"entity-type":"item","numeric-id":1160143,"id":"Q1160143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363116$B5967682-89A7-43F9-ABCC-4998F16FFDA3","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":"Q2363116$F4487980-FFAD-4496-8AEA-821AC35F795E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6c1243527c538ffa2794f311b50b82b3217e829","datavalue":{"value":{"entity-type":"item","numeric-id":504985,"id":"Q504985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363116$B084F50C-1603-4467-A1E9-4D28ACB135FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fab1b373895793d37ed441d8b74ec9c2d1774b9","datavalue":{"value":{"entity-type":"item","numeric-id":1197025,"id":"Q1197025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363116$BB9C9A61-A9AB-42E4-8A48-424823410F1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70b64c36f147f07e9132a04121c3023f0fae5bd8","datavalue":{"value":{"entity-type":"item","numeric-id":5539654,"id":"Q5539654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363116$73798FBF-CC27-4845-B730-1F2A13B69D56","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"6e8638e6e73070c5178a1a79faa4bddc7286a4d1","datavalue":{"value":"bafkreib6uexx4nricsg5wtarb4m4yufvi6hefjwfsbxsmlzozgo5hgb7km","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363116$9381AEB0-F287-4981-89E2-F208D3A5E540","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c6d40bbccdc77311ec5be7bd4ab94c7d2aee80d","datavalue":{"value":{"entity-type":"item","numeric-id":1633601,"id":"Q1633601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73684bfdfe578c9fa091d68e98ebfe17ce9e52f3","datavalue":{"value":{"amount":"+0.9080042","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":"Q2363116$A3F98595-F974-4745-8B08-CDA27F1BBAFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6316a9af6ff20abcdcd8efe5acc5fd9f6e19ab2","datavalue":{"value":{"entity-type":"item","numeric-id":2011144,"id":"Q2011144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f6d0b8c54ade62238324c83f6b41eb13d811b08","datavalue":{"value":{"amount":"+0.9067995","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":"Q2363116$A7539311-9950-4697-9471-5B51ABF099BC","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":"011f324974a54ad6e5837984abb0fcb673f97dcf","datavalue":{"value":{"amount":"+0.9061758","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":"Q2363116$BA014C3E-7FBC-47D5-B9C4-12FD29A8F396","rank":"normal"},{"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":"62a722d11b56498350b0d3b7693635e8e691b060","datavalue":{"value":{"amount":"+0.899295","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":"Q2363116$52B86E66-8461-4BB5-AAB1-1B90E922E42A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d395f4ed8bb3069b59b2e87272dda2aeaa230eb2","datavalue":{"value":{"entity-type":"item","numeric-id":3225711,"id":"Q3225711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"127f9aecc6c6ed541d5c247066a11fcb59bc8d52","datavalue":{"value":{"amount":"+0.89882183","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":"Q2363116$1232C5D9-158C-48CF-91E6-F608BFE043BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b81eb89f1fa1ecc9cc7fc58b9ed53b17dd758341","datavalue":{"value":{"entity-type":"item","numeric-id":2040019,"id":"Q2040019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26125dbc104f8631b2f92d9aa9c96af9a5a32756","datavalue":{"value":{"amount":"+0.89874274","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":"Q2363116$818E3B92-FDD5-4C6C-8C37-646ABA404CEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fb0d9d5ecda789a252e43716304d3047c06881c","datavalue":{"value":{"entity-type":"item","numeric-id":504985,"id":"Q504985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b40830198027c43edf09978e04569819af09e01e","datavalue":{"value":{"amount":"+0.894329","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":"Q2363116$5EC39919-0935-441B-882E-618F18ACDC1A","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":"78d990334e1ffc0cb10eecb34aa3de53427f4e06","datavalue":{"value":{"amount":"+0.88955337","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":"Q2363116$4B90F41D-143E-4174-B72A-4DDA1A840415","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1da133b47e948adbf3bc3edf627752617ec97e5b","datavalue":{"value":{"entity-type":"item","numeric-id":722311,"id":"Q722311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73850d6923b4ed1815657d1045c6324e20e5872a","datavalue":{"value":{"amount":"+0.8857619","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":"Q2363116$B42D8653-07C2-41D7-A246-94B4F33933D7","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":"fe3d792d460b2a9235fd04a22cc3300ee6b575f6","datavalue":{"value":{"amount":"+0.8839436","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":"Q2363116$CF4FF859-2C7E-46C2-8941-141BE12251F9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Induced_subgraphs_of_graphs_with_large_chromatic_number._IX:_Rainbow_paths"}}}}}