{"entities":{"Q1356774":{"pageid":1367513,"ns":120,"title":"Item:Q1356774","lastrevid":68542008,"modified":"2026-04-13T00:26:28Z","type":"item","id":"Q1356774","labels":{"en":{"language":"en","value":"Colorings and girth of oriented planar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1019120"}},"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":"Q1356774$CD2058A9-D358-48A1-A624-6030977C76CE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4060ebc020eb61ff1cc00e7379901d48bb31f227","datavalue":{"value":{"text":"Colorings and girth of oriented planar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1356774$C53CAAE4-6657-44B3-B92E-F0AB5C0584CC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ce948ec41dd8213c86499cc25b032810c7f59711","datavalue":{"value":"0873.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356774$08677D08-2F52-4C70-B596-58DA088A0683","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d78c34d5b0322afe9a85c436bac1e85fc7f9c3d1","datavalue":{"value":"10.1016/S0012-365X(96)00198-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356774$1FA92E28-1148-43F6-AB2E-F67CAF81F5C4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a34d7460ee6370363f9008097bc89d9a4353ddd3","datavalue":{"value":{"entity-type":"item","numeric-id":175612,"id":"Q175612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$C1806B53-1902-4A0B-872A-33ECFBDF249A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9380c4124a5ef272e2152da1b5d415130e3e64f8","datavalue":{"value":{"entity-type":"item","numeric-id":175596,"id":"Q175596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$48F97EB3-B5F0-4DB3-97BF-45B73110FFCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c147635d2f74f989c2abf2680ed671644a675820","datavalue":{"value":{"entity-type":"item","numeric-id":1112052,"id":"Q1112052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$A7ABF2F7-7042-4A56-AD7B-B3920C3AFADB","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":"Q1356774$CABBAA0E-AE55-44C2-9CF5-8C1BD7357106","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"412f7a31e42853d129270920f950562a85c36f4d","datavalue":{"value":{"time":"+1997-10-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1356774$E3E59DF3-417D-42BB-83B7-7F63190E3CD9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"453318b2e3f9c63743a25c034916385f48c6abea","datavalue":{"value":"Let \\(G=(V,E)\\) and \\(H=(V',E')\\) be graphs (possibly digraphs). A homomorphism from \\(G\\) to \\(H\\) is any mapping \\(f:V\\to V'\\) satisfying \\([x,y]\\in E\\Rightarrow [f(x),f(y)]\\in E'.\\) Here the brackets on both sides of the implication mean the same thing: either an edge or an arc. The existence of a homomorphism from \\(G\\) to \\(H\\) is denoted by \\(G\\to H\\). The following two problems are considered:   (A) The oriented coloring problem. Given an oriented graph \\(G=(V,A)\\), find the smallest number of vertices of an oriented graph \\(H\\) for which \\(G\\to H\\). This number, denoted by \\(\\chi(\\vec G)\\), is called the oriented chromatic number of \\(G\\). (Note that this is the same as the ordinary chromatic number if we consider symmetric digraphs as target digraphs.)   (B) The girth problem. Given an integer \\(g>2\\), determine the quantity  \\[ \\chi(\\vec g)= \\max\\{\\chi(\\vec G)\\mid G\\text{ is planar and has girth }g\\}. \\]  It is shown that every orientation of any large girth planar graph has oriented chromatic number at most 5. Furthermore, the authors classify those digraphs on 3, 4 and 5 vertices which color (i.e. admit a homomorphism from) all large girth oriented planar graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356774$A22A8BF8-146B-4207-85E2-980E00DE1150","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356774$8C8341F2-3BE3-4E55-ADCF-4BB191D6F1CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356774$26DDDD43-937E-4A09-A652-4E187BDACBA9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4930d2a1bc648da7deb693ba82ff78ec71249e4e","datavalue":{"value":"1019120","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356774$10A22EC2-0E90-4B69-80B4-804BC263F4AE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e636d6200f7544f4dd5a5bbed79f99982c70f6d","datavalue":{"value":"homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356774$E62607E0-8F1E-42FF-8829-90487A27C457","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356774$9785D31A-22A4-4FF4-A832-8A6AFDB77673","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0b781309ed6a51a3382fbae408803efbf8ce3be","datavalue":{"value":"oriented chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356774$B99A8AB0-B53D-4932-ACF7-F5EF622665B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ffa219ea2cff89df5162edb57bd2a31ea73e1a26","datavalue":{"value":"digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356774$C8938905-D4AE-44BF-91AC-5335BE673F60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a173748f93e4f70aa784451677e2ec88ea88e5","datavalue":{"value":"girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356774$A6D0DFE6-539E-4ABD-81CB-19ADAEAA829B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356774$18645E85-CD47-477A-9BCC-B1EB35FEDAFC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eee744981d92ac19b8d353f3a45a83ebd916fb73","datavalue":{"value":{"entity-type":"item","numeric-id":558237,"id":"Q558237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$94814351-E394-4D65-92D7-8ECA5418DA34","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":"Q1356774$8E8C0B4F-400C-4DCD-B567-7EFF0E23C9B3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9328fd3a34fb4b6ce7887fc52cf1e0cdef518e43","datavalue":{"value":{"entity-type":"item","numeric-id":4097312,"id":"Q4097312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$C03B1218-A20F-4DA8-B9B2-7739D5B61AF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ade5a5172a0b2dc9f519d61c7175134ee8bc199","datavalue":{"value":{"entity-type":"item","numeric-id":911612,"id":"Q911612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$9A08ED76-A208-4629-A0ED-765261A391AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f92dd856ac6e85d46c013684d1de479b1f38df9f","datavalue":{"value":{"entity-type":"item","numeric-id":1257487,"id":"Q1257487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$C1D3B9D2-8C61-4838-B734-A8F3F12D08BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61b5c47efe9ffc3dd4e3e9de3dd638c26801d78a","datavalue":{"value":{"entity-type":"item","numeric-id":5921616,"id":"Q5921616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$84885734-CA67-426A-87CD-25B4E7764EB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c367e0b7373b179fb1c166269ec2f59cc435e693","datavalue":{"value":{"entity-type":"item","numeric-id":1209287,"id":"Q1209287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$B01B6E38-3D9F-41CF-B795-79F0A6D73401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fec165abc7ade014841f417bcba31a647c17e0c7","datavalue":{"value":{"entity-type":"item","numeric-id":1100215,"id":"Q1100215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$49BC7E02-D989-467D-9CE9-D90B97C9D13E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d99101b30853333ff5ca3c17c825ec34ae9021e","datavalue":{"value":{"entity-type":"item","numeric-id":4889961,"id":"Q4889961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$EE726F27-AE43-49FB-92B1-DC108771FC2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ade08e5950cef3f4816d2a20486aaffb965cd270","datavalue":{"value":{"entity-type":"item","numeric-id":4878664,"id":"Q4878664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$A2993C6C-43AB-47D5-951C-10919C2D60F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9aa445d6582c3d63ac86f5d12027e0537ae8d21","datavalue":{"value":{"entity-type":"item","numeric-id":3686735,"id":"Q3686735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$D39AC39C-425B-4000-A26E-8EE9570E54C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11a4d21bdfb4786197a0884009912fca44edb8f5","datavalue":{"value":{"entity-type":"item","numeric-id":4200238,"id":"Q4200238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$20DFCA3C-76F0-4D99-BEB1-53EE9A98728C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"582bb2d8e7c3770c3184cd0ce6a793ab9d7bfd19","datavalue":{"value":{"entity-type":"item","numeric-id":3129826,"id":"Q3129826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$33AD5A54-46AD-4F77-904F-19F821F5EB97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c26050d258b183673b275b45306c6038c52bc7a3","datavalue":{"value":{"entity-type":"item","numeric-id":1155066,"id":"Q1155066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$70488A9F-994F-4A0F-A03D-CAAAF17E7B89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e03e0c440f0628d754f3c828c8e50f69a4edf0c","datavalue":{"value":{"entity-type":"item","numeric-id":4894618,"id":"Q4894618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$51349F39-D91F-43DB-A740-679B944B2424","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d912a8a8e4a90d11227a0ff617c145a8518c7138","datavalue":{"value":{"entity-type":"item","numeric-id":1334637,"id":"Q1334637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$45921A3C-087A-4C27-9A1A-1CD887245C8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca211d12a54bef7ee54f54df8169c7e2b38e90f1","datavalue":{"value":{"entity-type":"item","numeric-id":5942568,"id":"Q5942568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356774$006AFEC2-A9C0-41D8-BCE9-FA8CD5847D9F","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":"Q1356774$C9C8BC6E-9798-4619-8BE6-8E659F278B6D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"e43783b7d07c07a1c74d40ede8382f141ba11132","datavalue":{"value":"Q126529477","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356774$3AB4BB0D-7245-4A02-A0E5-4D6DC8CF53A7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ba88692252956f464d824809ba0035e8a4d5aab","datavalue":{"value":{"entity-type":"item","numeric-id":1025464,"id":"Q1025464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1fa1363640bf7287593dd7aa22954e066359783","datavalue":{"value":{"amount":"+0.8942065834999084","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":"Q1356774$FF7275C3-5EE5-423F-8798-614391160D22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ed56387a7445a7fad31dc2c0bdec05f043fd67f","datavalue":{"value":{"entity-type":"item","numeric-id":367080,"id":"Q367080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2eb3a660147f7f0e38f8078501ab694e7fcec89","datavalue":{"value":{"amount":"+0.8856199383735657","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":"Q1356774$CC82A49C-75F1-4B5F-9EEA-86F6B93245A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c1f1ebc65ae7972d55509787b4c5d24cb401f07","datavalue":{"value":{"entity-type":"item","numeric-id":2498117,"id":"Q2498117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"003ca426a1621f315874552149a24533807a02aa","datavalue":{"value":{"amount":"+0.8747747540473938","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":"Q1356774$2327D5B0-7ECA-496A-AAC8-823FDE5D860F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cdb3d6369d9c59f33c098c778ce2d61b6a29da8b","datavalue":{"value":{"entity-type":"item","numeric-id":845839,"id":"Q845839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"292248fdbb721dbc5e53438dacdf6e3a42559667","datavalue":{"value":{"amount":"+0.8710442185401917","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":"Q1356774$96243EF7-C524-433E-BE9C-13871935D892","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"945ac9fd5395522e62d50da22204d61185578ade","datavalue":{"value":{"entity-type":"item","numeric-id":2498114,"id":"Q2498114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01721520e3975960d47ade04045cb90746bdbe4f","datavalue":{"value":{"amount":"+0.8699628710746765","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":"Q1356774$ED35F75F-9744-4175-B541-55D2121FA368","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Colorings and girth of oriented planar graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Colorings_and_girth_of_oriented_planar_graphs"}}}}}