{"entities":{"Q2198407":{"pageid":2209150,"ns":120,"title":"Item:Q2198407","lastrevid":57775419,"modified":"2026-04-02T11:48:26Z","type":"item","id":"Q2198407","labels":{"en":{"language":"en","value":"List 3-coloring \\(P_t\\)-free graphs with no induced 1-subdivision of \\(K_{1 , s}\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7245967"}},"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":"Q2198407$BCB73B8E-6A68-48E5-AF06-24710E6DA02E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3d4cfe5047813db8ccdffab24f024aa0b1f68dec","datavalue":{"value":{"text":"List 3-coloring \\(P_t\\)-free graphs with no induced 1-subdivision of \\(K_{1 , s}\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2198407$D1143B8D-BBAA-4419-9F25-CECD0592AF1D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8123a4877c7762ed5c7d0d6c61574f9cc6cfc994","datavalue":{"value":"1471.05033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2198407$0AE0C435-31ED-4AFA-AAB6-EBC4A7D06360","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"86791d2de8f741697c1a28c841b5e520b1ea6f17","datavalue":{"value":{"entity-type":"item","numeric-id":256974,"id":"Q256974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198407$C6BC1960-9BE2-40E4-898E-37876FB0F488","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f84c2585906a3dfec8dc78c048cfc8b3b8be2285","datavalue":{"value":{"entity-type":"item","numeric-id":345122,"id":"Q345122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198407$B765C4F1-248D-4E75-BC88-07EC74E32068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"502fa3818c0729e7c2c4e3414e0aefd1ba7e2488","datavalue":{"value":{"entity-type":"item","numeric-id":1637132,"id":"Q1637132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198407$44339D92-AA69-4AEB-A656-C0EF47BC4D81","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":"Q2198407$0C40D659-2B14-408C-97EE-E017A5443B6C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"14a2bae8a6c91ebe59b7dcfd879b8f74b6b05d76","datavalue":{"value":{"time":"+2020-09-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2198407$07E974D1-59B7-41B1-B080-DA2896F615AA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0f3ed351dd6201c7b5930ad7ad445a141053b545","datavalue":{"value":"https://arxiv.org/abs/2006.03009","type":"string"},"datatype":"url"},"type":"statement","id":"Q2198407$FC8488C5-9E4B-4AEE-8307-601BBB6C6593","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c05d554bee02dd16dac05a1f8c8b87bff2000740","datavalue":{"value":"In this paper, a polynomial-time algorithm is given for the list 3-coloring problem restricted to the class of \\(P_t\\)-free graph with no induced 1-subdivision of \\(K_{1,s}\\). This complements several other partial results on a problem, which is well-known to be NP-hard in general.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2198407$432622B1-B339-4B3C-9842-CB1F8A28E4CA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5f0c3e74ef2a9cad4c650aec0242c10787729f41","datavalue":{"value":{"entity-type":"item","numeric-id":603121,"id":"Q603121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198407$E2B391DB-8FF9-4375-B505-5DF57B31FC18","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2198407$62A593E3-F67E-466A-8EEE-4B03AB52D0C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2198407$F6B5CBAD-9C68-40AB-B129-70A11DE9838A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2198407$95B1AEF4-0D9F-4C06-B602-A7970654B7B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2198407$A64E54C7-E552-4FA8-823F-A6E33F8A120D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"afaba65442e89cc4494daa5a8a376c4bafef51a5","datavalue":{"value":"7245967","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2198407$0E41790D-E2A4-4CC5-BB4D-17780C14EF87","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2198407$663BBDB2-1F45-4119-9419-66B3F5BB30FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f8854b5e4a0017c2e603242cf5eca1a042ef5e8","datavalue":{"value":"forbidden induced subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2198407$4021C33B-C2EA-47BE-8F4D-AC6F6DE2605B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2198407$543F947F-243C-4E0D-99F2-DB2AAB72E171","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":"Q2198407$971445B5-E7E5-449A-8E70-966BDE8499E3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d36f9a91461e62bcc2be438180319c1a72aa82ea","datavalue":{"value":"W3047788453","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2198407$90DD407A-C817-4FC1-B791-401BCDFDC55F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6a0d346506465223f8a96355556be48c1ad0dfb","datavalue":{"value":{"entity-type":"item","numeric-id":1786047,"id":"Q1786047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198407$D4D15D4A-12A4-49A8-B679-AED11EFD9983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35a44e11169a034de138802141ee5d73ec6d3d5a","datavalue":{"value":{"entity-type":"item","numeric-id":5236260,"id":"Q5236260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198407$8B98963F-29CD-4827-B083-84AF666CE9AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d4bd16b8f988e4232f1989a0f22132674569ade","datavalue":{"value":{"entity-type":"item","numeric-id":1079363,"id":"Q1079363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198407$C992481B-E0EB-420E-B419-5A7FF47E4709","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f08688ad89d97f94566d0f2d68d02ddad138796c","datavalue":{"value":{"entity-type":"item","numeric-id":2252529,"id":"Q2252529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198407$031C77E8-DEA0-459A-AA4F-319FDE08B55B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d8495d2a9835ba0228edbe74cd03d934b4b42b4","datavalue":{"value":{"entity-type":"item","numeric-id":2440105,"id":"Q2440105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198407$0B0159F2-E8B9-4D58-993F-7D80DBC5B649","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"977cd433ecde040f39e4c4dde1c0b893e5757f3f","datavalue":{"value":{"entity-type":"item","numeric-id":848637,"id":"Q848637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198407$10A9FBED-130F-4636-B27A-6DD3E0773CE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47707362ea38a9307252d6fd07d68a2560b06ac8","datavalue":{"value":{"entity-type":"item","numeric-id":499486,"id":"Q499486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198407$C1FB0BCF-BA29-4340-92A6-036AC38C2138","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"45946c8d430d56b67cb4353b91359a954a884be9","datavalue":{"value":"10.1016/J.DISC.2020.112086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2198407$7B876115-E648-4544-856D-E9E0AF00C979","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d232e0c1958c32d1756902a2b56316f4ee94a1a","datavalue":{"value":{"entity-type":"item","numeric-id":2234796,"id":"Q2234796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b91ecb5332b439aca87c488031ad6e1ac089ab28","datavalue":{"value":{"amount":"+0.8082807064056396","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":"Q2198407$56D5695D-9675-4541-880A-CDDF1A8C3918","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"410a9aeb3a904d44b5a7dbbde58e4a24eb92fbfd","datavalue":{"value":{"entity-type":"item","numeric-id":2182090,"id":"Q2182090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da007aaf0e2c5f421872af090e9cdd0b13109e88","datavalue":{"value":{"amount":"+0.7910476326942444","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":"Q2198407$05C009DE-0FD0-4F6E-B050-3DC052CA2A99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49271ccda4c94d5c5c40cf5060d8223b77c77541","datavalue":{"value":{"entity-type":"item","numeric-id":2223697,"id":"Q2223697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76524264ee975ae1b93a0fa9792f8c5b8bdadf89","datavalue":{"value":{"amount":"+0.7909190058708191","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":"Q2198407$612E9083-4144-4C80-B432-7B8B7473FE3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21bf1f4cef91f9a26a9654d06f0617c1e9943203","datavalue":{"value":{"entity-type":"item","numeric-id":1786047,"id":"Q1786047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cefa3455d6c72e8be49f48cc3fbd013e4c8b899b","datavalue":{"value":{"amount":"+0.7896685004234314","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":"Q2198407$7BF4AE66-A3DF-4A81-B9E2-244DA698773E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79b01078aee648da8ed38f25c58f198930a8033b","datavalue":{"value":{"entity-type":"item","numeric-id":5251642,"id":"Q5251642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1fe6a68bb9d18362488e545ef88b008c36cb4cb","datavalue":{"value":{"amount":"+0.7835269570350647","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":"Q2198407$8AD2A586-EBE1-468F-9D8C-11F6737671A2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2198407","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2198407"}}}}}