{"entities":{"Q1296984":{"pageid":1307734,"ns":120,"title":"Item:Q1296984","lastrevid":46677984,"modified":"2025-12-25T09:31:24Z","type":"item","id":"Q1296984","labels":{"en":{"language":"en","value":"Every circle graph of girth at least 5 is 3-colourable"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1320588"}},"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":"Q1296984$17DC3CCC-6CF7-435E-B2F1-1FF63953F471","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f4da20e8cd25ab640d94be310c32a76a6089bdc6","datavalue":{"value":{"text":"Every circle graph of girth at least 5 is 3-colourable","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1296984$6250B315-6AFE-4971-81BB-5D5006803AE8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"01caa31d5675cfca75832f6501c30df5126354cf","datavalue":{"value":"0934.05054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1296984$6FC51736-2575-4D88-8FE6-1B68F2D7750B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7fd96f1165c8c790771b63b2d66b98e3774ac9a6","datavalue":{"value":"10.1016/S0012-365X(98)00192-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1296984$92C283F9-1E70-4485-AAF6-743287EA045E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cde0da340f3f1442614a5bb0dfe5274443755ed0","datavalue":{"value":{"entity-type":"item","numeric-id":226451,"id":"Q226451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1296984$D92D7D9D-0CD0-4F8B-9F05-8BD0415532AA","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":"Q1296984$BCFCAF84-23FF-40A8-84F7-56652D36F81F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b78ba432cb77ac64be3ac5d97bd170fc19fe3117","datavalue":{"value":{"time":"+2000-04-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":"Q1296984$7AA56FE3-322A-4275-96AD-2BDCAC0EFCED","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"de7f1393ddf36607f6c20739b1225aea653924a0","datavalue":{"value":"The girth of a graph \\(G\\) is the length of a shortest circuit of \\(G\\). A graph is a circle graph if it is isomorphic to the intersection graph of chords of a circle. It was shown in [\\textit{A. V. Kostochka}, On upper bounds for the chromatic numbers of graphs, Tr. Inst. Mat. 10, 204-226 (1988; Zbl 0677.05027)] that every triangle-free (equivalently, of girth at least 4) circle graph is 5-colourable and in [\\textit{A. A. Ageev}, A triangle-free circle graph with chromatic number 5, Discrete Math. 152, No. 1-3, 295-298 (1996; Zbl 0854.05049)] that there exist examples of such graphs that are not 4-colourable. In the present paper it is shown that every circle graph of girth at least 5 is 3-colourable.   The main result of this paper is that every circle graph \\(G\\) of girth at least 5 is 2-degenerate---that is, every induced subgraph of \\(G\\) has a vertex of degree at most 2. From this theorem it follows that every circle graph \\(G\\) of girth at least 5 is 3-choosable---that is, for any assignment of size-3 colour-lists, one list \\(L(v)\\) for each vertex \\(v\\), there is a proper colouring of \\(G\\) which assigns to each vertex \\(v\\) a colour chosen from \\(L(v)\\). Setting \\(L(v)= \\{1,2,3\\}\\) for each vertex \\(v\\) implies that \\(G\\) is 3-colourable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1296984$4486B54E-CF03-4F14-80F2-B903EB9242A3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1296984$0EE0A594-08FE-4FA0-A13A-A559C9882202","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1296984$013A54BB-F3EA-46A4-8A20-1C451C4E8A6C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f9411b0eb0444fd76dca952ab9ea6390927f8fbc","datavalue":{"value":"1320588","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1296984$7FDDA406-2DEC-4D0E-A420-5B6895E09A68","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a173748f93e4f70aa784451677e2ec88ea88e5","datavalue":{"value":"girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1296984$8CE8D99E-8582-497A-BB54-067F4588DC13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20a5e1f1191acc6a9fe899dae84da95c86beb92d","datavalue":{"value":"circle graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1296984$E7C16B1B-BAB4-4D65-BB36-923166CD4E0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bc0d5058cf7773f67ff6548c4fa33edb07db16a","datavalue":{"value":"intersection graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1296984$E84F442E-9C55-4C2A-8DB7-C5FE57898CFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5c7ac22ba7810553a06c47c83d04d9fcad31fb75","datavalue":{"value":"colour-lists","type":"string"},"datatype":"string"},"type":"statement","id":"Q1296984$2643F891-9236-4F51-8A83-97E33620EF60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59e104fc9083dc8c4e491b340ba5128d82bfc9b1","datavalue":{"value":"colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1296984$EB318DBD-E8B0-4B2A-ACB5-9B3C38EDF9DA","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"5ed8c8d4cde68f5ec2c13a612a0602c0624c52ed","datavalue":{"value":"Q56503303","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1296984$0A065967-8FE9-4741-8488-079A8A304EEE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"457b59512685cc959c2dfec1eb05d289a709afaf","datavalue":{"value":{"entity-type":"item","numeric-id":442385,"id":"Q442385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1296984$7410D32F-EB51-432B-8C7E-DA22AE8B1FEB","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":"Q1296984$13427F97-7603-41AD-B70F-BDD147A8EDE3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0a61a45e1ade602828ce4b4756469271c494d5d","datavalue":{"value":{"entity-type":"item","numeric-id":1917502,"id":"Q1917502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1296984$A9DFB23E-DEC2-46BD-B347-DE172F7306EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e2ea2a7f71d2c376d34542a583769554c7d6b93","datavalue":{"value":{"entity-type":"item","numeric-id":1061132,"id":"Q1061132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1296984$7874AF13-F947-40BA-AA9A-5BC10E117759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35184f581a4fa42ee779b59d5e27eea0c204219f","datavalue":{"value":{"entity-type":"item","numeric-id":5931450,"id":"Q5931450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1296984$844A7950-A5E9-454B-99C4-EAE3B1B07FD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7fd41b0ffa9bc1b1dfebba1430a30e841f9c297","datavalue":{"value":{"entity-type":"item","numeric-id":3832590,"id":"Q3832590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1296984$4FA3D8BC-7496-40EF-ACDC-A504A4EAB2EC","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"63c79d2d5d7cb30a3a5228db7034b845b78e95dd","datavalue":{"value":"journals/dm/Ageev99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1296984$6679AA18-F9C3-4B09-8BE1-115DF3E84D6A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8abd2c1f7dd5c32d1b23b43d8758f08b7c34281a","datavalue":{"value":{"entity-type":"item","numeric-id":5900070,"id":"Q5900070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ffb45674107896a86e5f86a363041380c45b7c5","datavalue":{"value":{"amount":"+0.8801432847976685","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":"Q1296984$CDAB3703-CD99-40FC-9454-880FEA0F6337","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9faacc5def137495e3fdceaa44e3a770c26a0ed","datavalue":{"value":{"entity-type":"item","numeric-id":5743553,"id":"Q5743553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9015f34953ecf3bab62c98a108689bd7702443aa","datavalue":{"value":{"amount":"+0.8723902106285095","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":"Q1296984$9D81D26A-7677-477E-8A3B-7D8932C6C0C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f7773b4b527e35702c6a77c6c962d6004e43435","datavalue":{"value":{"entity-type":"item","numeric-id":1917502,"id":"Q1917502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0430a73f30bd49afb12715eb10233c9922420c0","datavalue":{"value":{"amount":"+0.8079203963279724","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":"Q1296984$DD46F958-B242-483C-BE59-FF7BE66EAE4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee654850fcd7da8e77e9c923a1e23353c17ea051","datavalue":{"value":{"entity-type":"item","numeric-id":1892853,"id":"Q1892853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06d5ca60b5ceee43f1ff0dbad62ae661fc54d661","datavalue":{"value":{"amount":"+0.7970367670059204","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":"Q1296984$C279E9B3-E431-40F2-983F-BF747F4F7021","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1296984","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1296984"}}}}}