{"entities":{"Q2664564":{"pageid":2675307,"ns":120,"title":"Item:Q2664564","lastrevid":57975777,"modified":"2026-04-03T07:39:00Z","type":"item","id":"Q2664564","labels":{"en":{"language":"en","value":"Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7428778"}},"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":"Q2664564$D4C967CB-E12A-4F80-8814-CBF50D435D26","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"798744bd57d4a991757ab138650d6eb8ceb4cb21","datavalue":{"value":{"text":"Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2664564$B8263BA0-A5C5-4F18-A7BF-957AFB699512","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5ff2c9855d77de900e7f65d28d854f74ae457d31","datavalue":{"value":"1484.05066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2664564$198250AF-C94A-4F10-86B5-24B2B3D40B0E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0344539925c30eafc8102699adfab87d48c82922","datavalue":{"value":{"entity-type":"item","numeric-id":213911,"id":"Q213911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664564$AEA032FB-4469-4DCE-8F49-B08B4AB510D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"53427ddbb10f2ef6b2b23d5d0945110660ad7953","datavalue":{"value":{"entity-type":"item","numeric-id":273100,"id":"Q273100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664564$E1ECB076-267D-405D-B341-C8C0211238CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c767c73643f6f9c229d2e29427c218355d7fa9cd","datavalue":{"value":{"entity-type":"item","numeric-id":186136,"id":"Q186136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664564$2F9E896B-8C7A-45A6-9420-297A54FE6BD9","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":"Q2664564$2C50ABB9-F27F-4C8C-AB83-6A85E5EF2B9F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9b583c20d2ff6d94455cad03e479bb4858d4835b","datavalue":{"value":{"time":"+2021-11-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2664564$0665810E-E7C1-4753-A816-69FE71A258B1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a3017ee822a75b2143d3a50c4ddc36b49d53eb55","datavalue":{"value":"https://arxiv.org/abs/1601.01197","type":"string"},"datatype":"url"},"type":"statement","id":"Q2664564$E4AB6E6F-209C-4F01-A265-EBFDD582C1D7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b73e9f6b135861b6ddb2a1cfad07897ea0a14a8f","datavalue":{"value":"This paper deals with 3-colorability of triangle-free graphs embedded in a fixed surface. More precisely, it is the last work of a series from the same authors on this topic. In this paper, the authors provide a linear-time algorithm to decide 3-colorability; in case of a positive answer, a quadratic-time algorithm can be used to output a 3-coloring. Such algorithms also allow to set the coloring of a bounded number of vertices in the given graph. \\par For Part VI see [the authors, ``Three-coloring triangle-free graphs on surfaces. VI. 3-colorability of quadrangulations'', Preprint, \\url{arXiv:1509.01013}].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2664564$7C775BBE-7728-458C-8B83-E32707DAE80F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1d1c0541113cdf2565b18624f920ca42eda2491f","datavalue":{"value":{"entity-type":"item","numeric-id":2117520,"id":"Q2117520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664564$5B61302E-9623-4B15-B17F-68908D92E3D1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2664564$83BB6198-CBAB-41E7-9CB4-10F24471807B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2664564$7E990E84-48DB-42E6-98F2-73D98B80ECB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2664564$D275C295-91AB-43D3-A00E-CB0043104217","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a0b6bb7b690913244c6cd175311c409c947ccc1b","datavalue":{"value":"7428778","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2664564$6958DF77-3AC0-42C2-8787-13D1C0FADDF3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2664564$95431EF6-E8B6-45BA-A219-FEC4B68B33C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"82e10b106979077ac626034ec385c48041ecfb89","datavalue":{"value":"surfaces","type":"string"},"datatype":"string"},"type":"statement","id":"Q2664564$510B399E-0573-4D69-BA6D-D17607C70600","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed35a9fa19458304c0b74dd4e65451fe88c0a624","datavalue":{"value":"triangle-free","type":"string"},"datatype":"string"},"type":"statement","id":"Q2664564$4870C7E9-C05D-40E7-9190-FD254CEBCB4A","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":"Q2664564$78C208B1-273D-41AF-8366-624D5FBEF4C0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1b573475685b8e5636fe8ae2ea8c0d4c3c9d9bdd","datavalue":{"value":"W3184638075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2664564$38DBAA5F-BAD1-4993-8080-1CA336A9F471","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"27ae5d28526dbcf269b5462aa2b5af4905e84159","datavalue":{"value":{"entity-type":"item","numeric-id":3189025,"id":"Q3189025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664564$6B560CCA-F3AE-4C14-81AB-272364F1AF0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"859ac532b345546c73ff0603e65dd474a52a4024","datavalue":{"value":{"entity-type":"item","numeric-id":723878,"id":"Q723878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664564$800BE19A-0F72-4447-B5CE-37068C234DCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2e87e8a1655c2084120406aae07b8eeac6f89e8","datavalue":{"value":{"entity-type":"item","numeric-id":2200929,"id":"Q2200929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664564$CF166CB4-40E3-49DB-BCD6-34563345A672","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54ba92fd26c7bdf80b70ec2dee03757c2e90e469","datavalue":{"value":{"entity-type":"item","numeric-id":2040021,"id":"Q2040021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664564$EFD05427-78CF-4071-A24C-7B0CE5CD5097","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8878f4918b9611618979b470abbd8a49a94e429a","datavalue":{"value":{"entity-type":"item","numeric-id":4601215,"id":"Q4601215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664564$7EAA87B5-A322-47AC-A173-CFD1A0838A77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6327224c4debc2501c4439bfd0d53425e1e3cd69","datavalue":{"value":{"entity-type":"item","numeric-id":4505015,"id":"Q4505015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664564$77DC7FE8-06A5-4068-9950-33851836D049","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664564$BE2F020A-C3CC-4AC2-B7E6-FC007CC8B7BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbbb32b7075575c1cb0708f2127f8e393f0d8c07","datavalue":{"value":{"entity-type":"item","numeric-id":3220606,"id":"Q3220606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664564$AC4A39DA-2A4D-4E90-BF59-75F9F0A1CFAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0dc92a48f606c97189f828b1d0dd00a1308d9efb","datavalue":{"value":{"entity-type":"item","numeric-id":4255804,"id":"Q4255804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664564$785F2545-AD02-4EB8-B037-497597A94D9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d722e527436ab92c2de5bc5648be33aaffc90bf6","datavalue":{"value":{"entity-type":"item","numeric-id":1403910,"id":"Q1403910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664564$A4C13ABB-AB88-44ED-AF16-7FE7F62DBCCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a180e9bd460d853592c5fd5751f344626d5419ee","datavalue":{"value":{"entity-type":"item","numeric-id":4865530,"id":"Q4865530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2664564$2E27E2FE-5B83-4492-BAEA-9A89E1E57A0F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f95478085d90ce6102955ae09825fef4865d6d66","datavalue":{"value":"10.1016/J.JCTB.2021.07.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2664564$A302857D-CE82-46E2-A99A-AEBBFB41BBB7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3644dfe5a286211fdf20b3a4f92def2938fdf585","datavalue":{"value":{"entity-type":"item","numeric-id":4633818,"id":"Q4633818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"451fced3516f8cb315a135c071486b2b82bc397e","datavalue":{"value":{"amount":"+0.913769543170929","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":"Q2664564$2A4D2B9F-3C34-4C41-BBCB-109C4239EEED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"577b93f79f3fbb907307347fd5fa4475e3fdfeec","datavalue":{"value":{"entity-type":"item","numeric-id":4633932,"id":"Q4633932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d082fa8b47bb8f63f9f6a9d6479e4ae7d2bfe177","datavalue":{"value":{"amount":"+0.900536060333252","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":"Q2664564$3C3A938F-B4CD-483F-B12B-D201F49BDDC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad28e38e881de7b00a03680f19134d01c49dc532","datavalue":{"value":{"entity-type":"item","numeric-id":3189025,"id":"Q3189025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04f517413c572d30619bf8f907982031e29f580e","datavalue":{"value":{"amount":"+0.8971258401870728","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":"Q2664564$918E45EA-A648-4CFE-89E2-653FE918A9F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34ea8d68e43770628bff974bab298c644414a2aa","datavalue":{"value":{"entity-type":"item","numeric-id":1957652,"id":"Q1957652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"405d37768cebad31d8893fb1668aa872d685e7c7","datavalue":{"value":{"amount":"+0.8734391331672668","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":"Q2664564$A02C3E86-D9ED-48A6-AEB6-359631EA4AA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0cb6672b58111289c103f5ea430bd33350c4fe7","datavalue":{"value":{"entity-type":"item","numeric-id":5464602,"id":"Q5464602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d2ac278392fe8f9b718103d806923bd95c20762","datavalue":{"value":{"amount":"+0.8463073372840881","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":"Q2664564$D2EFDB66-1530-4BF5-B563-E05DBD56485D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2664564","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2664564"}}}}}