{"entities":{"Q1369650":{"pageid":1380390,"ns":120,"title":"Item:Q1369650","lastrevid":70769646,"modified":"2026-04-13T16:46:20Z","type":"item","id":"Q1369650","labels":{"en":{"language":"en","value":"Color-critical graphs on a fixed surface"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1076872"}},"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":"Q1369650$BEC3A25E-EFE5-40E8-A380-F6D83B3429F4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dc91440f53ca9fc9012651275550cb5790c72912","datavalue":{"value":{"text":"Color-critical graphs on a fixed surface","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1369650$52B2D838-1FA1-4E9A-A528-3EDF35D71E9C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ad22cc07cd19e6d379c6ccdc76790286c2a95004","datavalue":{"value":"0883.05051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1369650$98BB0F3F-B273-4DEC-A646-8C1C564418C0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aec857263cee52fe850f36c12f5157e5c8f0a013","datavalue":{"value":{"entity-type":"item","numeric-id":228790,"id":"Q228790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$1B6B6ECF-09C6-41BE-A9BE-D82610123F46","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":"Q1369650$7C3117B2-D361-4A46-8E6D-82E3C27871E7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a312114d760b266d81c4b64e43f5fe758eba402f","datavalue":{"value":{"time":"+1998-02-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1369650$B06F1290-667E-4BF1-81AE-2F20DAE1CE6C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"94c757e530b2986bd759257ab3b95ca482350be5","datavalue":{"value":"A graph is \\(k\\)-color-critical if its vertex chromatic number is \\(k\\), but every proper subgraph is (\\(k-1\\))-colorable. It is known that for each orientable surface \\(S\\) and for each \\(k \\geq 7\\), there are only finitely many \\(k\\)-color-critical graphs on \\(S\\). On the other hand, there are infinitely many 5-critical graphs on each surface \\(S\\) except the sphere.    In this paper the author shows that for each orientable surface \\(S\\) there are only finitely many 6-color-critical graphs on \\(S\\). He also shows that if \\(k \\geq 5\\), then there exists a polynomially-bounded algorithm for deciding if a graph on \\(S\\) can be \\(k\\)-colored. The techniques involve cutting the surface and graph to transform it into a planar graph, then applying various 5-coloring results for planar graphs. Some extensions of the results are given where a small subgraph is pre-colored, to list colorings, and to non-orientable surfaces.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1369650$A86ECC78-5EF8-4CAF-A187-E9FB8DF3A4F7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1369650$6839F900-04A4-4219-9F40-6F762D7F1693","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2e540114ed97ae270ae1e288351fa4e3fe085b78","datavalue":{"value":"1076872","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1369650$F5BE16C5-5232-44CF-96BA-B07F8BAE3325","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1369650$3E2A65C8-87FB-43F8-B3AF-35BC20575B9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f39d7fc3fc364a43a70204f0de54dd2c811a56b","datavalue":{"value":"surface","type":"string"},"datatype":"string"},"type":"statement","id":"Q1369650$18447861-0B6A-4FD4-8724-29C661FFE272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0fcce008177189cafd371672d7c3ec3fea8aaa1","datavalue":{"value":"sphere","type":"string"},"datatype":"string"},"type":"statement","id":"Q1369650$F4A1B5D8-FA58-4ACA-B8A4-6EAE9CD8028B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77e4ab8cc373f12e52ca72a9484a9fb6022ad7b2","datavalue":{"value":"color-critical graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1369650$DC029699-261D-4349-9557-605FAA3897E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1369650$EB9E9E4E-E8DD-41AA-A920-F783DBB73715","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"245bb46b54951018ca725c73286f7f519e3b12ac","datavalue":{"value":"colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1369650$9F6452BB-CE21-4332-959E-2FA652656F64","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b687a818ec58a93e77f94a71ec71ff4e2750b160","datavalue":{"value":{"entity-type":"item","numeric-id":592090,"id":"Q592090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$3829222F-E9C1-435D-A314-7BD62D8B99F3","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":"Q1369650$143A301A-2052-41E0-A09C-B2D1FF40A430","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ac2bcdc04a1aacddfac85a4e1941ef150f482c20","datavalue":{"value":"https://doi.org/10.1006/jctb.1996.1722","type":"string"},"datatype":"url"},"type":"statement","id":"Q1369650$177FC836-4612-4018-A942-0831B1C67F4C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"44a139d36e2aabcf23d65274c3c82bc83c87d9ea","datavalue":{"value":"W1978313715","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1369650$66A52BF5-AC98-421E-A3C8-C2F7AE1D6664","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bab18833f1d3cb3c170df8f40171e63d12e6fd00","datavalue":{"value":{"entity-type":"item","numeric-id":3666872,"id":"Q3666872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$DBBD0C56-194D-4DEC-9FFC-BF9C70EBE20D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72acf0a8c828beb0701174c8bd66cec9ffb9c319","datavalue":{"value":{"entity-type":"item","numeric-id":3688408,"id":"Q3688408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$BCBD28E7-5421-4549-B56D-6F0625039B74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c837da2ca835eb3ccea4c3ff35b00c88bde3a596","datavalue":{"value":{"entity-type":"item","numeric-id":5518140,"id":"Q5518140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$E44EDAB5-30C6-4682-A9BD-BB70C6C93FE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a14a86f8a741965bd20330ff99006349c570540","datavalue":{"value":{"entity-type":"item","numeric-id":1188966,"id":"Q1188966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$382D47BA-A4CE-404B-8862-F2C4FB3449F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"871464b325516ba832b6553c5449feaf17d9bc79","datavalue":{"value":{"entity-type":"item","numeric-id":5819950,"id":"Q5819950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$69B21F58-A4D5-4027-BFEE-2F4E3807BE22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3573b87026595a32002fa2dc54ac8b096bc29f3f","datavalue":{"value":{"entity-type":"item","numeric-id":3922703,"id":"Q3922703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$38FADDF4-7DBA-4C27-8892-C1FC4E88A9D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcef6a9bf99d271d6e6038e95f87e95dcbfe45a6","datavalue":{"value":{"entity-type":"item","numeric-id":1239165,"id":"Q1239165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$BB3FC5C0-4FA3-4AD2-9C09-044E5C127FC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccf1d962f65c4400b3eafbc31256816f056be207","datavalue":{"value":{"entity-type":"item","numeric-id":1238328,"id":"Q1238328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$8FBEE1F9-E57A-4765-900A-CBC61E9DAA4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f08c5112edf7f837490d497bb2f3820e4c72b45","datavalue":{"value":{"entity-type":"item","numeric-id":5732334,"id":"Q5732334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$A4828A7D-A8A3-4AC2-ADC5-D436F6DBF570","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":"Q1369650$072AE9C1-3336-45C1-8DCC-FFDAD686E34B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e31c4207af522bbd991cbbfd2180e7357a576da8","datavalue":{"value":{"entity-type":"item","numeric-id":4372592,"id":"Q4372592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$8A3742F1-86FA-4611-A729-AC54DCE1B134","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b13e3feb35c4a5abd77e6190b5cd58c6bc20fc04","datavalue":{"value":{"entity-type":"item","numeric-id":1126188,"id":"Q1126188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$EE05C5A2-2631-4CA3-B6E2-8B66A5897146","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f855246caf01e7d423da5ddcd02591be6660a7f0","datavalue":{"value":{"entity-type":"item","numeric-id":4857375,"id":"Q4857375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$1D89C374-1E40-4B7D-86D3-B20E96D6B54D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fec3b5e0d657d9f4ea613c8648365bfacb54b529","datavalue":{"value":{"entity-type":"item","numeric-id":4141836,"id":"Q4141836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$1DF6E451-CF49-477B-80DE-958256623823","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f41d49e608d5ffc8abc77bd4e4e561119c3c473e","datavalue":{"value":{"entity-type":"item","numeric-id":1142781,"id":"Q1142781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$FD7BFAE8-9E70-43A1-9472-D5CAB597A8DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f269cca585ea9aaef73ae9ec7d458105296b993c","datavalue":{"value":{"entity-type":"item","numeric-id":916669,"id":"Q916669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$FF0ED3ED-A9DE-4BB4-8B06-86D1C5B2A85E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f83aa8534c3def810eaaf07e152abff6514fbf7","datavalue":{"value":{"entity-type":"item","numeric-id":1321998,"id":"Q1321998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$CCB5A95C-A629-43E1-8DD0-DC9167A855F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1d628995dc1792ccb01723af24c6bf902d9c188","datavalue":{"value":{"entity-type":"item","numeric-id":1333321,"id":"Q1333321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$D3B9D6EF-5274-4F0E-9FFB-DC29B561E1AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8e9a01d057f2ac8669e7cac2ad5d67b6775d2fa","datavalue":{"value":{"entity-type":"item","numeric-id":1333334,"id":"Q1333334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$8B439161-8204-49CE-997E-156F57C418EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15ad9390e562161170f09ba03f501d30d2aa5310","datavalue":{"value":{"entity-type":"item","numeric-id":687126,"id":"Q687126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1369650$9328C68A-29E2-492E-885F-492C9864BE45","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d70eb192effd619376a4bb9eee140501ecc1133c","datavalue":{"value":"10.1006/JCTB.1996.1722","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1369650$7524427B-A8AD-4BC2-8207-AEC8035C6704","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5330de4a49188a1c275c7ca125b69da93f6a3f41","datavalue":{"value":{"entity-type":"item","numeric-id":4633930,"id":"Q4633930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5d9658396d8d457a5db83b7686e43df3c241d18","datavalue":{"value":{"amount":"+0.8479776978492737","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":"Q1369650$75EB75F9-9111-4260-9658-807B3C189F69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ed7fe2d8c290314b99583197297469b434c154c","datavalue":{"value":{"entity-type":"item","numeric-id":1210575,"id":"Q1210575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"794195865c32e30b7c91ef5e30346517fc063a65","datavalue":{"value":{"amount":"+0.8451465368270874","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":"Q1369650$7FFF2D48-68E0-4A60-B44B-3CCC4A1270EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb2cc6c14a093d30bd6dc1b23945bc297ee611ba","datavalue":{"value":{"entity-type":"item","numeric-id":1403910,"id":"Q1403910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc77b3d7c104e7b6792f9d007a26b426d01a88d1","datavalue":{"value":{"amount":"+0.8421371579170227","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":"Q1369650$4C05012A-E9A7-4F76-ADDE-22A6CBF4E717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d48dcf34a57c539eaad554dbc8ce41e5ea412f4","datavalue":{"value":{"entity-type":"item","numeric-id":2822588,"id":"Q2822588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52c427708dc12d9455418c04516be6a9fc2f9dca","datavalue":{"value":{"amount":"+0.830879807472229","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":"Q1369650$408C9B9F-9E05-4A65-A22C-6A814145F46C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6840f92a8d2a6a888b8eb0d5d09c657dbc6c6bd4","datavalue":{"value":{"entity-type":"item","numeric-id":856865,"id":"Q856865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0abc262c5b72a6f095025f783685a1afb14af92a","datavalue":{"value":{"amount":"+0.8227238655090332","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":"Q1369650$50226E2D-43B7-4E0F-A48C-7366CB7EF566","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Color-critical graphs on a fixed surface","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Color-critical_graphs_on_a_fixed_surface"}}}}}