{"entities":{"Q6143691":{"pageid":13277998,"ns":120,"title":"Item:Q6143691","lastrevid":39861596,"modified":"2025-01-27T19:11:14Z","type":"item","id":"Q6143691","labels":{"en":{"language":"en","value":"The chromatic number of a graph with two odd holes and an odd girth"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7783962"}},"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":"Q6143691$B86A8212-CC3B-41C6-A42E-F5C2DFC9FEA3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1200196b213c97f340b8eeea59bf2131bf7af3d9","datavalue":{"value":{"text":"The chromatic number of a graph with two odd holes and an odd girth","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6143691$28DD71E6-3499-4E1E-B86A-3B1689657C63","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"076e4063b00b2fa65d753cf6618865b5ad2b3f93","datavalue":{"value":{"entity-type":"item","numeric-id":2109107,"id":"Q2109107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6143691$88F1EC5A-96AD-439F-A8EC-010B0F909345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b7176a293f70b356c9547431caedfc84b544740a","datavalue":{"value":{"entity-type":"item","numeric-id":6046761,"id":"Q6046761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6143691$EE71D091-C35A-4A63-87B2-2A22510A9406","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6143691$30A005EA-A657-413C-8318-CBDB4ED691B5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ea7c0c2bbacdb03a6451b2e40513a7d25057a30a","datavalue":{"value":{"time":"+2024-01-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6143691$5A2BF69F-BEDB-4CA0-AAB1-EF9D1B5E2973","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e5f0a48f78622df8106c2040f5445098804a7308","datavalue":{"value":"For \\(\\ell \\geq 2\\), let \\({\\mathcal{H}}_\\ell\\) denote the family of graphs that have girth \\(2\\ell +1\\) and have no induced odd cycles of length different from \\(2\\ell+1\\). Moreover, \\({\\mathcal{G}}_\\ell\\) denotes the family of graphs \\(G\\) that have girth \\(2\\ell+1\\) and any induced odd cycle in \\(G\\) is of length \\(2\\ell+1\\) or \\(2\\ell+3\\). In the last few years the chromatic number of graphs in \\({\\mathcal{H}}_\\ell\\) was intensively studied. \\textit{B. Xu} et al. [Electron. J. Comb. 24, No. 4, Research Paper P4.32, 8 p. (2017; Zbl 1373.05071)] proved that graphs in \\({\\mathcal{H}}_2\\) are 4-colorable. This result was just recently improved by \\textit{M. Chudnovsky} and \\textit{P. Seymour} [J. Graph Theory 103, No. 3, 437--450 (2023; Zbl 1522.05237)] who proved that graphs in \\({\\mathcal{H}}_2\\) are 3-colorable. Moreover, \\textit{W. Di} et al. [``The chromatic number of heptagraphs'', Preprint, arXiv:2206.01400 [math.CO] (2022)] proved that graphs in \\({\\mathcal{H}}_3\\) are also 3-colorable.  In this paper, the authors study the chromatic number of a larger family, namely the chromatic number of graphs in \\({\\mathcal{G}}_\\ell\\). They prove that for an integer \\(\\ell \\geq 3\\) any connected graph \\(G \\in {\\mathcal{G}}_\\ell\\) has the property that the subgraph of \\(G\\), induced by the set of vertices that have the same distance to some fixed vertex, is bipartite. This result immediately implies that all graphs in \\({\\mathcal{G}}_\\ell\\), for \\(\\ell \\geq 3\\), are 4-colorable. Finally, they show that each graph in \\(\\bigcup_{\\ell \\geq 3}{\\mathcal{G}}_\\ell\\) with radius at most \\(\\ell\\) is 3-colorable.  The authors conclude the paper with an open problem about an upper bound for the chromatic number of graphs in \\({\\mathcal{G}}_2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q6143691$928CB6E6-D296-4D78-892C-21FA24C944A9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"512183e69be4ab0f9c803f93e55f4d9b77753376","datavalue":{"value":{"entity-type":"item","numeric-id":504963,"id":"Q504963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6143691$0DCB47C6-025E-490A-9AA2-69987B3053AC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6143691$F9951E5F-04A0-4300-B861-12109E91ABBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6143691$37DAB211-9C9D-485C-8D67-FC75B437B51B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6143691$0371B35B-9340-4A52-BF88-597074AD2601","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6143691$3A2D0945-7391-4092-BACB-FF473228E58B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e3935ac9350cac6e19f9e445adcf5a1352976f12","datavalue":{"value":"7783962","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6143691$239E30ED-9A6A-4DE5-AB0C-74CD58360EC5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q6143691$39D2621D-FD3E-4B9F-B33B-5F0A595BF217","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a173748f93e4f70aa784451677e2ec88ea88e5","datavalue":{"value":"girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q6143691$40FA715C-85FD-403B-BBA8-D14E99B64604","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0781dea49020fd5028774cbbf789a94ac1263f85","datavalue":{"value":"odd hole","type":"string"},"datatype":"string"},"type":"statement","id":"Q6143691$30C1E947-B0D0-4E81-B4D9-DAE9FEA09F4C","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":"Q6143691$51C7F61D-DBCA-4019-BC3A-604388D0B52C","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":"Q6143691$354BE472-54C1-435D-AA91-DD276BDB369B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b1c167be6cff784d50b80f7d76ee8d8f3f335a6","datavalue":{"value":{"entity-type":"item","numeric-id":6074589,"id":"Q6074589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6143691$8F889FEF-8AD5-44B7-AD45-6F6A7BD1ADE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8d01759c16f1e263ef4f4ee34349121058f9979","datavalue":{"value":{"entity-type":"item","numeric-id":2109109,"id":"Q2109109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6143691$2AD20208-C0F5-4500-8120-BDD90B409C13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32f921a433b457f554eb39c29b4d7dc305705c90","datavalue":{"value":{"entity-type":"item","numeric-id":625382,"id":"Q625382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6143691$D3ACE2C9-74AA-47BD-BD37-9B0CDA92B0EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b00c4ecf2223115b84a58231fb53818a716e4423","datavalue":{"value":{"entity-type":"item","numeric-id":405121,"id":"Q405121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6143691$0051639C-773A-4DFA-9572-6ADBF2C7291F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5325820f1da9bdbe993d9d54d34a90dc88d69e8e","datavalue":{"value":{"entity-type":"item","numeric-id":4869540,"id":"Q4869540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6143691$41FD8FC4-1632-4354-A6B6-53FD381FF554","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0dcf28010177e6dac09e8ed0411b7ee6e6372e7f","datavalue":{"value":{"entity-type":"item","numeric-id":1676794,"id":"Q1676794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6143691$12A5D0DE-7764-4C03-8126-D8F4C0E379F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23bb644b977acffa90f052e3fdf7300cc6cae5d5","datavalue":{"value":{"entity-type":"item","numeric-id":6041512,"id":"Q6041512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6143691$3DF12C10-7E12-4EAF-BD6B-BC6293716E66","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8de4e9c3ae2e182872ed9e13dd6cd71a68f9dd88","datavalue":{"value":"10.1007/S00373-023-02723-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6143691$27C3CA3D-81B7-47A9-9B6A-2E5C5E3CCBAE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a47745adb3a971e13d5c461263a255187a97adb4","datavalue":{"value":{"entity-type":"item","numeric-id":2109109,"id":"Q2109109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61c9accb721f7edfed509b9b65e946e12839b9fc","datavalue":{"value":{"amount":"+0.8004996","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6143691$9622E9B1-F6F4-4A2C-ADE8-BCE69C4236AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f882f74c7113ae9152365c01369f708c2a8a79fe","datavalue":{"value":{"entity-type":"item","numeric-id":4906312,"id":"Q4906312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83b4d75e7c4b78131165ed8e08c6a2ad0974b317","datavalue":{"value":{"amount":"+0.73718655","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6143691$4C6B75FA-9F7F-4AC0-AF3D-6ACC62C15806","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cafde1bdfe3dfb68f7a56baba8a664d9942d85b8","datavalue":{"value":{"entity-type":"item","numeric-id":3088283,"id":"Q3088283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"512a560178829765abb4c1a8db6a662279025902","datavalue":{"value":{"amount":"+0.71624255","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6143691$016404A2-3413-4300-A30A-EBF6D05AA5F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58c312be4453ee57bc933576b72ed1d21867f2ac","datavalue":{"value":{"entity-type":"item","numeric-id":1883263,"id":"Q1883263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee2bf051e9bce2fa0364d11eb9bbadfca4f42626","datavalue":{"value":{"amount":"+0.71345735","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6143691$BE6B574B-D3C6-47D6-B690-93363B017A2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a408ea2c258b7e7070da95ce35a7fd714db722f2","datavalue":{"value":{"entity-type":"item","numeric-id":1100214,"id":"Q1100214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"deb54bd67c36985cfda9cbd4e8ea457ebb19a5d8","datavalue":{"value":{"amount":"+0.71270806","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6143691$60251B41-29F3-40D6-9A3B-91C64DF931C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0dc242d183a1b4969fa371b1924ea85318765b7d","datavalue":{"value":{"entity-type":"item","numeric-id":3744191,"id":"Q3744191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aab542d1fce2fd68fa9822ca109a2cb966206554","datavalue":{"value":{"amount":"+0.71176696","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6143691$5D6F9925-60A9-497D-B597-19628711AF94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa380f8d71f06d63c6538dd23483b522f584dcdf","datavalue":{"value":{"entity-type":"item","numeric-id":4602857,"id":"Q4602857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"404be6f4d53e3f94c4a8150694d1f969233c2f75","datavalue":{"value":{"amount":"+0.70990527","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6143691$5A2BEF72-08F0-4A19-835D-0ED0366CB27B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a0e8b239293673eeea5ba8bfd1a9afc35004838","datavalue":{"value":{"entity-type":"item","numeric-id":3514226,"id":"Q3514226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc98afc8718d8577d9683c76f6fd2ee4f43999cd","datavalue":{"value":{"amount":"+0.7080821","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6143691$C7B58ACB-E744-451C-8989-3B9FCFE56485","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"222bb6d5de090c229f2cca408332a6601693433d","datavalue":{"value":{"entity-type":"item","numeric-id":4906278,"id":"Q4906278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b9f70660162df89ebd5da311ad59202736915dc","datavalue":{"value":{"amount":"+0.7020319","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6143691$427D18B5-569D-49EB-A182-F92D0262EDDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ae16c449b0d7e9dbec3f3a9df39533bbbf9245d","datavalue":{"value":{"entity-type":"item","numeric-id":4854635,"id":"Q4854635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2407faaafa608f83eb7e780a9eb91a7a4c0a37bc","datavalue":{"value":{"amount":"+0.70158917","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6143691$01928E86-2EB7-42C5-8FCD-72E5766C9C30","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6143691","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6143691"}}}}}