{"entities":{"Q1403910":{"pageid":1414650,"ns":120,"title":"Item:Q1403910","lastrevid":67362078,"modified":"2026-04-12T17:06:53Z","type":"item","id":"Q1403910","labels":{"en":{"language":"en","value":"The chromatic number of a graph of girth 5 on a fixed surface"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1967937"}},"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":"Q1403910$8A436A6D-279B-4BEC-8503-5217EBBB62FE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b1aafed999dc80d646646035b8c0d281a73747e0","datavalue":{"value":{"text":"The chromatic number of a graph of girth 5 on a fixed surface","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1403910$45FAD1B5-5884-4932-B3F4-9167BC7E92D1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c55c5857571008a10293de30a632576b399e079c","datavalue":{"value":"1020.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1403910$CB2ABC72-0103-4328-8C89-02817B0963E3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aeee0fc93bad61a221bd19f5b1471fd358d44225","datavalue":{"value":"10.1016/S0095-8956(02)00027-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1403910$86BEE929-ADD8-465D-80D2-75EDF5DBFD93","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":"Q1403910$5BFB20DA-F2E3-4FFE-9815-0531F2090857","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":"Q1403910$38319F45-EFB6-4C14-B4FD-930F99400333","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ef5551d0bed39d732a1be7431b699cbb7e704fe8","datavalue":{"value":{"time":"+2003-08-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1403910$94B150B2-F6A6-4F0F-8A9E-4036A52EADF0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0f74097dd9327ebb600d29296a1f90270dac762e","datavalue":{"value":"In this interesting paper it is proved that, for every surface \\(S\\) and every natural number \\(k\\), there exists a natural number \\(f(S,k)\\) such that the following holds: If \\(G\\) is a graph of girth 5 on \\(S\\), and \\(H\\) is a 3-colored subgraph with at most \\(k\\) vertices, then either the coloring of \\(H\\) can be extended to a 3-coloring of \\(G\\), or else there is a small obstruction containing \\(H\\), that is, a subgraph \\(H'\\) with at most \\(f(S,k)\\) vertices such that the coloring of \\(H\\) cannot be extended to a 3-coloring of \\(H'\\). In particular, there are only finitely many 4-color-critical graphs of girth 5 on \\(S\\), as a 4-color-critical graph of girth 5 on \\(S\\) has at most \\(f(S,1)\\) vertices. It follows that, if \\(G\\) is a graph of girth 5 on \\(S\\), and all noncontractible cycles in \\(G\\) have length greater than \\(f(S,1)\\), then \\(G\\) is 3-colorable. The result is best possible in the sense that there are infinitely many 4-color-critical graphs of girth 4 on \\(S\\), except when \\(S\\) is the sphere. As a consequence, it is deduced that the chromatic number of graphs of girth 5 on \\(S\\) can be found in polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1403910$EE48A7C2-54CF-4B54-BEB4-BA4F860938FE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1403910$59A30A44-F5E8-4B48-B3EE-6B7BE9A8C30F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d75a6150e3999821120fce0ccf88057a134c13f5","datavalue":{"value":"1967937","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1403910$77B4858E-CF34-4F58-8ACD-40B2C88B1CE4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67e867e7139e3c007a15345d9f8412a809ada436","datavalue":{"value":"4-color-critical graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1403910$7B6A8420-1FDE-4D66-B55A-4AF1C3ACD62A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1403910$62ED8D2A-DBD2-4063-890D-2C2089259DF3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1403910$CD5EAFE9-6CCC-4C5B-A838-9363EC2565C7","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":"Q1403910$BA97D6D6-1242-41DE-BC8D-37B235D35601","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1403910$F7B45030-8040-4032-86E0-2217C61B3E5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a776c4516ceca81fac148ce42f4ae05589e2756","datavalue":{"value":{"entity-type":"item","numeric-id":1322020,"id":"Q1322020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1403910$866AC598-EC82-47A9-AE88-E2EC961974B2","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":"Q1403910$64E009F2-261D-47ED-B854-DC0139C9D588","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":"Q1403910$2AD931A3-7FC0-43AD-9637-B08CA22783C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb8ef170bab2eecea4df93c99065c01ef4b984ac","datavalue":{"value":{"entity-type":"item","numeric-id":757398,"id":"Q757398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1403910$0BACE612-D034-45CB-90DE-A4647B5CBCC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9799935fa6b5975808f92cfcc703600c2e6e3c88","datavalue":{"value":{"entity-type":"item","numeric-id":2726740,"id":"Q2726740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1403910$E8B49ABD-8D2C-4EF7-8776-D27CF7E81BAE","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":"Q1403910$0974B73F-5D77-46B0-98E6-8726DAF62E14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187399749b9cbddae3c82e16af59c0db2746c526","datavalue":{"value":{"entity-type":"item","numeric-id":1338317,"id":"Q1338317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1403910$F56F0B40-6FC6-4F77-B06C-E4B341C06222","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bec1ea839bbae95cce4f38ddbbba08521d102f9","datavalue":{"value":{"entity-type":"item","numeric-id":1892853,"id":"Q1892853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1403910$B2254CEE-C460-45A3-9022-78ABA2773512","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54c0fddb60ef50c63bc9e9644d6899672b42df2c","datavalue":{"value":{"entity-type":"item","numeric-id":1369650,"id":"Q1369650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1403910$D8A81523-2F48-4371-903F-51F28F30BFA8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e4c65a5388d85634311c70c24f0d94d07ecac45","datavalue":{"value":{"entity-type":"item","numeric-id":1405112,"id":"Q1405112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f7a2d60cf15a82664a0929ac247bee632322cf8","datavalue":{"value":{"amount":"+0.8520233631134033","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":"Q1403910$9E8DAAEB-5E64-45D4-AC03-99B52FC2AFEE","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":"9f7a2d60cf15a82664a0929ac247bee632322cf8","datavalue":{"value":{"amount":"+0.8520233631134033","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":"Q1403910$B717E887-9408-4102-B4B2-67C2D960326B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1836d03fb382651a6c08adc9ee9bd1808b7c7cb4","datavalue":{"value":{"entity-type":"item","numeric-id":1369650,"id":"Q1369650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1154da66b2e4b7e81fd7d0e10725a1024a50f6c","datavalue":{"value":{"amount":"+0.8421374559402466","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":"Q1403910$BB34F3CB-F200-49AA-AACE-1070E391F930","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8072835a2d0c188fa5b0a8de69529ae99519d83","datavalue":{"value":{"entity-type":"item","numeric-id":1322020,"id":"Q1322020"},"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":"Q1403910$983C87BC-25AF-46AC-9DC8-4DF6881A2D5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7dd5caa19517af8fcd9654dd3d746f1b1607ff0b","datavalue":{"value":{"entity-type":"item","numeric-id":4372592,"id":"Q4372592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17d83198973c9647471f33b9c057df7178b5c62a","datavalue":{"value":{"amount":"+0.8336527347564697","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":"Q1403910$887FADE6-759B-4C1E-8A1E-78D1F27ECD7F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The chromatic number of a graph of girth 5 on a fixed surface","badges":[]}}}}}