{"entities":{"Q2124227":{"pageid":2134970,"ns":120,"title":"Item:Q2124227","lastrevid":54297581,"modified":"2026-01-26T14:32:34Z","type":"item","id":"Q2124227","labels":{"en":{"language":"en","value":"Vertex coloring \\((4K_1\\), hole-twin, 5-wheel)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7509394"}},"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":"Q2124227$C1D19324-D752-428E-8419-BFEFF3E4BA7D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"835383f0e7e81fa39883ef87643bc741dd546524","datavalue":{"value":{"text":"Vertex coloring \\((4K_1\\), hole-twin, 5-wheel)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2124227$3B53785A-146C-4D3A-BB1B-420D446AA86D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1049ece187276ed5f0b8c7bdbb249c4a1f033e60","datavalue":{"value":"1493.68263","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2124227$B76C20A1-76FD-4CD1-8AB7-3EE4D01E1C3F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5e59b93bafc5505ef21665aeca142f593a5e8d68","datavalue":{"value":{"entity-type":"item","numeric-id":2091796,"id":"Q2091796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$5BD26D01-B19C-4D88-9D66-4CE457B246F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"73c7b32642174f98c751bacef398f0e87fb4c13f","datavalue":{"value":{"entity-type":"item","numeric-id":1663801,"id":"Q1663801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$C5755872-C5A6-4588-937A-4BE2E34F8D65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7598b946dc98bf1d17807d2ef3a244f2419361f8","datavalue":{"value":{"entity-type":"item","numeric-id":234396,"id":"Q234396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$EA791891-D6F5-4A5C-96D0-45089378E747","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$51CA9031-0E0B-4BA6-A5DF-382ED4D58A0E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3442da576695aca4488c92172c85d1c7d8dc1fc9","datavalue":{"value":{"time":"+2022-04-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2124227$BAB35368-A3C8-464E-BDCB-E3C3A312CA73","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9a4ed8b806cd337b8f2b0b5af4f28760a3678152","datavalue":{"value":"A hole-twin is the graph obtained from a hole by adding a vertex that forms true twins with some vertex of the hole. A \\(5\\)-wheel is the graph obtained from a \\(C_5\\) by adding a vertex that is adjacent to all vertices of the \\(C_5\\). The authors show that a (\\(4K_1\\), hole-twin, \\(5\\)-wheel)-free graph is perfect or has a bounded clique width. As a consequence they obtain a polynomial-time algorithm for the VERTEX COLORING for (\\(4K_1\\), hole-twin, \\(5\\)-wheel)-free graphs. This is another class of \\(F\\)-free graphs for a given set \\(F\\) of graphs for which there is a polynomial-time algorithm for the VERTEX COLORING problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2124227$ED69E4DC-52A3-4936-A971-B6E46DE3856B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2124227$A35D5E08-3931-4716-81D9-24DF29FEB6CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2124227$A8AD1540-19AE-4963-8817-C0278DCF3C48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2124227$380FAD96-123D-4248-AA39-ADF90B76604D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2124227$05B9D558-79E6-4918-AA47-8653C7286EE1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"74c1ac5e6446a2a52931d8ca08473998cad8f2e0","datavalue":{"value":"7509394","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2124227$9E175659-7BAB-4E4E-AAC8-074E7C618B76","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2124227$477BDEF1-EFFF-44E2-9E3F-405FF9D62C04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2124227$9E30AAD9-768B-494B-AE72-930C8742BD44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c879ffdfbc2bd9661bf8b8f33fe926464dd99a5","datavalue":{"value":"hole-twin","type":"string"},"datatype":"string"},"type":"statement","id":"Q2124227$3932EEF2-D878-4357-A58B-2F67ED9B2989","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e124859dde7fb46597fe2d0aef17a0438c12c510","datavalue":{"value":"5-wheel","type":"string"},"datatype":"string"},"type":"statement","id":"Q2124227$AE55A127-B117-4E15-9A85-42B0DDC8F10B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4241d06a5ad40c81408acdad1396e5c461f38e81","datavalue":{"value":{"entity-type":"item","numeric-id":831023,"id":"Q831023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$3517AF2E-1C47-47D7-9D70-9CE11C925B60","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":"Q2124227$56B64564-2E10-402F-A720-82137C919B54","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"79679a4d80964c08a17dabe68fa6bbf3af19f91e","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2022.02.009","type":"string"},"datatype":"url"},"type":"statement","id":"Q2124227$A9DC9E9C-7160-43B0-A2B7-9C69191F6363","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"990a3f843f1f75d05234eb833c480bfff9de7e61","datavalue":{"value":"W4212817891","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2124227$1DE6FD02-FF3A-45B0-84A3-915E089E9D48","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f63e38e4851ca0e3a13042d4f415c0b9fe4f5434","datavalue":{"value":{"entity-type":"item","numeric-id":5601346,"id":"Q5601346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$FB5387E5-6695-4B7D-AEFD-1242697C3F2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8a74f042ba1f29a12a670ab9d659cf777707121","datavalue":{"value":{"entity-type":"item","numeric-id":798301,"id":"Q798301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$847D75C5-A145-493E-B357-0DB0CF4A9AEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8385c17945fa9e7e6a271669b4ab7b025700e7dc","datavalue":{"value":{"entity-type":"item","numeric-id":2432547,"id":"Q2432547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$588E2AB4-4B8D-4A50-BADC-277BAEB883EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c20e0b8b69bb74bc107c5a48305e78f34c64cd1d","datavalue":{"value":{"entity-type":"item","numeric-id":2494439,"id":"Q2494439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$486258A7-0E0D-4720-9AA6-DA57B58E57F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb824d887f98dd74ca6f1faa806c22f8d63b3d0e","datavalue":{"value":{"entity-type":"item","numeric-id":855256,"id":"Q855256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$1841EE9E-5FEF-42AB-97F4-806F687AC99A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"211530a7d66720062b60e82cf130f31beea4a662","datavalue":{"value":{"entity-type":"item","numeric-id":1975365,"id":"Q1975365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$B8165E50-53BA-4281-BB1C-F430663ACF13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8fe56184955dbba620e4cb94dc309dfe37fcc19","datavalue":{"value":{"entity-type":"item","numeric-id":1974445,"id":"Q1974445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$19B92676-70D5-4ED9-AACB-61F5D48EF660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"306d2b6a499169e4a40f9cc6468d6223c720d652","datavalue":{"value":{"entity-type":"item","numeric-id":2132368,"id":"Q2132368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$35AD93A1-1488-4C0E-B758-64A1E68AAB3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd0452d5965289ec4a793d2bc82a916b9c039fed","datavalue":{"value":{"entity-type":"item","numeric-id":1686052,"id":"Q1686052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$3B9D107D-C393-4120-B8F8-B639DE047929","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d058c9b7075c0d1008aa799dc9e46eef022fc4f3","datavalue":{"value":{"entity-type":"item","numeric-id":2403803,"id":"Q2403803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$863D174F-CA84-444E-9D2C-BD4A685007E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b07b5dcf0b43c9f49e2d29db88bee73b1cb11be","datavalue":{"value":{"entity-type":"item","numeric-id":1886097,"id":"Q1886097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$2F530361-41DF-4935-942E-F19C8811948D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70932f1cf740819121b6dff2db80775f668b9c68","datavalue":{"value":{"entity-type":"item","numeric-id":3216686,"id":"Q3216686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$8C80C5FF-19A5-47F4-B800-5C632FD853CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aeea9c759438b4c0998879473dd96339053db2a4","datavalue":{"value":{"entity-type":"item","numeric-id":344868,"id":"Q344868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$7FAAA013-59BE-42B3-BC6D-4B38765D3D02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfe38c2659c530c62454eb53f4cfa7e3703b9346","datavalue":{"value":{"entity-type":"item","numeric-id":884481,"id":"Q884481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2124227$13950442-6FC1-410F-98DC-D3BAD883D743","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fe70b615a8fc7590060ca881756c2eb21b4d561c","datavalue":{"value":"10.1016/J.TCS.2022.02.009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2124227$F1EFB828-265E-48D1-873E-21169AC72798","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4bdbba5b44f2880bfd9fada591aae1940066b5aa","datavalue":{"value":{"entity-type":"item","numeric-id":1686052,"id":"Q1686052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8983525387a4e4113900d800303145e6f10e68b","datavalue":{"value":{"amount":"+0.8255767822265625","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":"Q2124227$CA4C502B-BC76-4D72-8A5E-8C417D1E55F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f4258bb9648db355cba2edaf16f4ab3843ec56a","datavalue":{"value":{"entity-type":"item","numeric-id":6057651,"id":"Q6057651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6b0e9378564937198af7aca1c07192dfe165f4a","datavalue":{"value":{"amount":"+0.8195834159851074","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":"Q2124227$EC6A3459-853C-4EBD-BBB9-88E6FC92A87F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87eb65573d4490f0606fbfc22fe9c5b76179ce0c","datavalue":{"value":{"entity-type":"item","numeric-id":2113346,"id":"Q2113346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"473623413577435957138ef78ed5d27c254b9d00","datavalue":{"value":{"amount":"+0.8162407279014587","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":"Q2124227$5AAC39FC-BB89-416B-9136-31F624068BFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"792b16d8f4d6f730078cd235f0ecd8edcdfa0a18","datavalue":{"value":{"entity-type":"item","numeric-id":2403803,"id":"Q2403803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82adc89fc95614f3f95b38a5480eabb983c89fef","datavalue":{"value":{"amount":"+0.8151016235351562","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":"Q2124227$EA842B5D-C799-439E-9702-D58F9A6FB22A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"855b565cb489042f2dc4e871eae6ce8ac49d6415","datavalue":{"value":{"entity-type":"item","numeric-id":2158304,"id":"Q2158304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d140b2e72536740e9a985d050b6a4c91cb456eb2","datavalue":{"value":{"amount":"+0.8135284185409546","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":"Q2124227$88CAC232-E3DE-4C18-971A-58441ABAE561","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2124227","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2124227"}}}}}