{"entities":{"Q1010717":{"pageid":1012565,"ns":120,"title":"Item:Q1010717","lastrevid":69413925,"modified":"2026-04-13T06:50:22Z","type":"item","id":"Q1010717","labels":{"en":{"language":"en","value":"Avoiding rainbow induced subgraphs in vertex-colorings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5540917"}},"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":"Q1010717$9D862C12-16CE-42F4-8984-9296D1ECA347","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0c356338329c3858551cc4afd932caf8bb9d4b22","datavalue":{"value":{"text":"Avoiding rainbow induced subgraphs in vertex-colorings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010717$AC3A6340-3DA9-4BF0-B9EC-001B024FE9F5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"facd32796f28c562443b6ab804fde52348e6c376","datavalue":{"value":"1180.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010717$4606A259-0606-492A-B0CD-8356FB206BD4","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":"Q1010717$7A123646-4369-4160-9F05-7023469498CC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1010717$109B0756-0FAC-4287-967E-72042F8205C1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7579ecf143f6533a188e14cc8c5ba29f42a134c4","datavalue":{"value":"https://arxiv.org/abs/1605.06172","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010717$3D4EF0D3-4231-4A88-A504-2D5CB3DC3581","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"010e2a5d0fea7741af06f5d214fca0f16807ab84","datavalue":{"value":"https://eudml.org/doc/117213","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010717$AF598E07-1F31-48ED-A5DA-25310F3C70EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"504019fd675e0ae27192b757d7d3387dcaf84ff1","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r12.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010717$9B18E860-7074-4A92-9155-ED118091EF66","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0b3cb1b7be7b5ef8bb0d3b594e03b90f97501a28","datavalue":{"value":"Summary: For a fixed graph \\(H\\) on \\(k\\) vertices, and a graph \\(G\\) on at least \\(k\\) vertices, we write \\(G\\longrightarrow H\\) if in any vertex-coloring of \\(G\\) with \\(k\\) colors, there is an induced subgraph isomorphic to \\(H\\) whose vertices have distinct colors. In other words, if \\(G\\longrightarrow H\\) then a totally multicolored induced copy of \\(H\\) is unavoidable in any vertex-coloring of \\(G\\) with \\(k\\) colors. In this paper, we show that, with a few notable exceptions, for any graph \\(H\\) on \\(k\\) vertices and for any graph \\(G\\) which is not isomorphic to \\(H, G\\nrightarrow H\\). We explicitly describe all exceptional cases. This determines the induced vertex-anti-Ramsey number for all graphs and shows that totally multicolored induced subgraphs are, in most cases, easily avoidable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010717$61F58233-221E-49F0-9610-FEBF8530BE4F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010717$D305E5C8-C8D2-4355-A0B9-A1147664AF61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010717$3A3960FE-D974-4C9A-A1C4-406E0B1E0514","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3e16d10ae7d043f3bdfd6fd7f05f09260409f47e","datavalue":{"value":"5540917","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010717$80616C3E-3671-4A6E-9926-7A79C2ECF894","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"28f64772242ab082b0a4e7456e0833b0af243b1d","datavalue":{"value":"unavoidable totally multicolored induced copy of a graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010717$38C9C9AC-DC66-46D3-9646-B95A61CC88DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db333fe11f996482881a8e675daabd0e7088faa0","datavalue":{"value":"induced ver tex anti Ramsey number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010717$9DC48DD8-0FDA-466F-96D0-57EA75537A20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85dfdbd7a975d6137b355769addaba184ea21dc4","datavalue":{"value":"vertex coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010717$D474DA5D-430C-47A0-85BF-F2CA856BF007","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb988c1f12f55e37b16cb0e92a60065d846438a9","datavalue":{"value":"avoidable totally multicolored induced subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010717$28A0CAA1-D61B-4B1B-9B47-EF4589FE529E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f2fdadb67de69217412ac18bc215234e7f62ae74","datavalue":{"value":{"entity-type":"item","numeric-id":1398252,"id":"Q1398252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010717$04839817-A018-471B-9424-534D669D5AE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"15796c0873d9a05767b939c2bba042c56c00920f","datavalue":{"value":{"entity-type":"item","numeric-id":313785,"id":"Q313785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010717$CB1AC189-B2BD-4084-82BC-429678EF700E","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":"Q1010717$59A4DCC9-9B19-4776-9DC7-6EADE67EFB99","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"740f986eed53edaca1e539bc4e187faf89398270","datavalue":{"value":"bafkreidier4j2iravkoms6t7dto25ob5yo3a2otst5zazppxzm44mfggu4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010717$E821E577-C669-4B06-A318-610F9D4FD3B4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a699037e388cf8cba8efc7cb851e6dbea669d85","datavalue":{"value":{"entity-type":"item","numeric-id":3635530,"id":"Q3635530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a8f546a3047592f8803de6d200755d42339c544","datavalue":{"value":{"amount":"+0.98348576","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":"Q1010717$14331182-EEFE-43E0-827B-ACDB7270F9CE","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":"c81c701666c40b8f5c83239c27c2bf1a00cba4ad","datavalue":{"value":{"amount":"+0.9452175","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":"Q1010717$6FFCD0E5-96E3-4AEC-86EA-0696B4DAC52B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df332edf5ee6cc7dbde6a7c5794d94a88ff34691","datavalue":{"value":{"entity-type":"item","numeric-id":339490,"id":"Q339490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b31d63dc50943f3b4998816222f70d4a67bc6028","datavalue":{"value":{"amount":"+0.9320451","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":"Q1010717$BEFA48F4-2FC8-4032-B29E-97624A6BEB6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d75d4551a08531b654fbd25a216e0c5009adde8","datavalue":{"value":{"entity-type":"item","numeric-id":942100,"id":"Q942100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1717467c58b982ecdf42de89a2bedee51aef8b00","datavalue":{"value":{"amount":"+0.9315815","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":"Q1010717$7FBC1603-A81B-4A3B-ABCB-BB8BDB3F3C32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f604ecbb6ecff997686fab0a86e5e428b3157d2e","datavalue":{"value":{"entity-type":"item","numeric-id":527226,"id":"Q527226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0aa099d3dfb41fd8562217b426fb55a1873cda9","datavalue":{"value":{"amount":"+0.92329776","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":"Q1010717$69099EA7-FD04-4B8B-BA37-B7821A6FE709","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"661133ca1bedaada6fe4509e533fd223e91af0ee","datavalue":{"value":{"entity-type":"item","numeric-id":4590881,"id":"Q4590881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c81319047e8009b47a861c17ae8a55ec759462a3","datavalue":{"value":{"amount":"+0.9225994","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":"Q1010717$7BC4E669-6C7C-4D3E-BEA3-2BD34580772B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"835dae1884cc71578dd1a47c279d15306ab97af9","datavalue":{"value":{"entity-type":"item","numeric-id":2380463,"id":"Q2380463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b7146afaf4aef0c47cefcbc25644717582f37ec","datavalue":{"value":{"amount":"+0.92190945","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":"Q1010717$55DE8570-1D63-4520-A863-B20AB560E88F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a065b9a9f6a9c8fc50388260fea235dcf72804e5","datavalue":{"value":{"entity-type":"item","numeric-id":3553235,"id":"Q3553235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f72a8acf68392ef6069327389e1ca76566771752","datavalue":{"value":{"amount":"+0.9204725","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":"Q1010717$CCA6E077-3430-4A24-AB99-86728CB49F52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4d5ce60c3896460db9bc62ab763322e6412ea25","datavalue":{"value":{"entity-type":"item","numeric-id":3990220,"id":"Q3990220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00cb96801d7d37e5a549bd8816d9159c8e3905fe","datavalue":{"value":{"amount":"+0.9201963","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":"Q1010717$8473B47C-7D18-4574-8380-78F9D43C50C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fbad6fb4f46e93e1cb728571471a1083e0c8d3d","datavalue":{"value":{"entity-type":"item","numeric-id":3139750,"id":"Q3139750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f10058ce4622ca2a5e7e10c91d1032019a21195d","datavalue":{"value":{"amount":"+0.91994077","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":"Q1010717$24819066-48D1-458F-850C-AF047382714F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Avoiding rainbow induced subgraphs in vertex-colorings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Avoiding_rainbow_induced_subgraphs_in_vertex-colorings"}}}}}