{"entities":{"Q2497471":{"pageid":2508214,"ns":120,"title":"Item:Q2497471","lastrevid":44210133,"modified":"2025-11-20T21:18:29Z","type":"item","id":"Q2497471","labels":{"en":{"language":"en","value":"On the oriented chromatic number of graphs with given excess"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5043681"}},"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":"Q2497471$72DE7131-CEE0-4AD6-ABB3-449F4B83F718","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d5c43986a86e3c000b96b7df7be29721d71520e4","datavalue":{"value":{"text":"On the oriented chromatic number of graphs with given excess","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2497471$1EAAFA45-07C5-455D-82CA-26DCD20A77E7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cce765d1920726963a1b20d012dcf867b639c1d3","datavalue":{"value":"1145.05022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497471$CC2331C6-B5F4-4398-A160-8F1BBFE137A2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c675352d8a42ebdc1538a9a94dcfc11bd7d726b6","datavalue":{"value":{"entity-type":"item","numeric-id":844209,"id":"Q844209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497471$F4D20781-3519-4405-B74D-0B13637FBB66","rank":"normal"},{"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":"Q2497471$8C7404C5-A115-4BE5-8530-F8683B16BBB5","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":"Q2497471$60AE2961-47A0-44D8-A80B-ACD64C1AD628","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fb876cd0509c83d752b9ca15b7a238c782dbf5de","datavalue":{"value":{"time":"+2006-08-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2497471$3A9A23B9-33C5-466E-BCB4-4F4B552105E0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1db302186f2c4d8e04808939807a1164aea18367","datavalue":{"value":"Given an oriented graph \\(\\vec{G}\\) (that is, a directed graph without opposite arcs), the oriented chromatic number \\(\\chi(\\vec{G})\\) of \\(\\vec{G}\\) is the smallest integer \\(k\\) for which there exists a mapping \\(c:\\;V(\\vec{G}) \\to \\{1,2,\\dots, k\\}\\) such that, for each \\(uv \\in E(\\vec{G})\\), \\(c(u) \\neq c(v)\\) and, for each \\(uv, wt \\in E(\\vec{G})\\), \\(c(u) = c(t) \\Rightarrow c(v) \\neq c(w)\\).  In the paper under review, the authors study the ordinary and the oriented chromatic number of undirected/oriented graphs with given excess (that is, the minimum number of edges whose deletion results in a forest; this invariant is called also the cyclomatic or Betti number, or the dimension of the cycle space of a graph). They prove that each unoriented graph \\(G\\) with excess \\(k\\) satisfies \\(\\chi(G) \\leq \\frac{1}{2}(3 + \\sqrt{1 + 8k})\\) and the bound is tight. Further, they prove that the oriented chromatic number of oriented graphs with excess \\(k\\) is at most \\(k+3\\) except for graphs having excess 1 and containing a directed cycle on 5 vertices (which have oriented chromatic number 5); the bound is tight for \\(k \\leq 4\\). Finally, it is proved that, for oriented graphs with excess \\(k \\geq 3\\cdot 2^{n-1}(2n-3)+4\\), the oriented chromatic number is at least \\(3\\cdot 2^n - 1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2497471$E144E000-7A66-4AD1-9C15-D98EA25F9E6F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf552a6496a70699f2802e7f7eff6309238b43f4","datavalue":{"value":{"entity-type":"item","numeric-id":383766,"id":"Q383766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497471$60388D7E-B598-419D-8E1A-C7D68B188239","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497471$AD77A11A-F2C2-4810-96B4-4C50DAF73027","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"74fac97c59901a3abbc34974c8810f976a9232cf","datavalue":{"value":"5043681","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497471$45920C0C-C379-4AA8-B4D6-17B360186544","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2497471$59F642E9-7DE5-4E8F-897F-3AA953A4B350","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58712acbde860c0153062a2693545d5f45b74754","datavalue":{"value":"graph homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q2497471$9EE9A3D7-D9C9-40B5-9BEA-A014C0B425EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2572e32cd2fbf3cc089964860141c88c524ee766","datavalue":{"value":"oriented graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2497471$38A74F75-5EE5-44E7-AC35-87682054085A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9492f7c0d20d7f4a64d59ac61f24980e45b73097","datavalue":{"value":"Betti number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2497471$603AE414-B671-4EEE-9B6A-79EFE76DD65D","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":"Q2497471$8A970F62-EC89-44CC-8597-F17D5D95573D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9a4bc5acba083f696d67458999e184a123f2e85f","datavalue":{"value":"https://doi.org/10.1016/j.disc.2005.12.023","type":"string"},"datatype":"url"},"type":"statement","id":"Q2497471$959FF016-C8E0-41FE-8703-AE69B4E7EAD7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ef456587c94f4e6fd13a4251cbf62d366e32c355","datavalue":{"value":"W2085650440","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497471$5F3BC319-98E1-4729-942F-60AD240835F5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497471$AA31F418-2FDF-4648-A702-A42AF52EF076","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c03c0ebdbaaa3fa8b3c3b957fd1ef3ca9e60ce11","datavalue":{"value":{"entity-type":"item","numeric-id":1850516,"id":"Q1850516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497471$1C28A287-1EBD-46FD-8179-599978FA989B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b439d6b5ea1e767aee9f4d150fbcd4d20c87b7f4","datavalue":{"value":{"entity-type":"item","numeric-id":1336623,"id":"Q1336623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497471$62BE7845-51A8-4181-89AC-035ADC1E0572","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":"Q2497471$0AF618C7-4731-49E8-9F76-87F0F54CA184","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":"Q2497471$7937C177-07D0-4CCB-A258-2F4CC00A28D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19950609e2df16fbd7728a2406ede1b13f42b5dc","datavalue":{"value":{"entity-type":"item","numeric-id":4344206,"id":"Q4344206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497471$8DAAE99B-A9F6-464E-9E55-725B7472C879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"587368c273cee1d0cd0520545ef7ad6bc44dce2d","datavalue":{"value":{"entity-type":"item","numeric-id":5931459,"id":"Q5931459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497471$A7F5F446-02DD-4FED-B95A-EAECDFAF7CD9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cbff1426e093d56c3eae274d5401caedf1ba3ad7","datavalue":{"value":"10.1016/J.DISC.2005.12.023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497471$FD8CBCA9-5D9C-4DA9-9079-F7ED3D8BEF12","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e235053404f55e74b8cefbffca68ba9b703dd36","datavalue":{"value":{"entity-type":"item","numeric-id":4344206,"id":"Q4344206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ca3e2804629f8fdb9db3fbed82c037f9a7caf2c","datavalue":{"value":{"amount":"+0.95049936","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2497471$45558A1C-59C2-45DD-AB8B-4AE0BCE5AFDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb21ebfee2de99a86d8aec93b73068f5acd79d26","datavalue":{"value":{"entity-type":"item","numeric-id":3558604,"id":"Q3558604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f313a4c35a34bb5f0d8e2cbcbf9824b47294bd0","datavalue":{"value":{"amount":"+0.94153357","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2497471$9C99B339-13C7-4142-8F72-D9DDB77ECFFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9ba8738a5371a103877ca19d317ef8cd8f2b9f5","datavalue":{"value":{"entity-type":"item","numeric-id":5387018,"id":"Q5387018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b408717d6762344d360f9a97ae896efbf70a3cc3","datavalue":{"value":{"amount":"+0.9366558","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2497471$464853CB-899E-4849-9FE8-ED1BF06EDA68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"665aa872f6675c0ae5cc58a07313eb9720d80b27","datavalue":{"value":{"entity-type":"item","numeric-id":2410109,"id":"Q2410109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"968d0862931d2671938370cc7eef109959408bd1","datavalue":{"value":{"amount":"+0.93647087","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2497471$AD55BE17-3954-4FAC-94FD-C708594E4D81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b94d3aa57ebf8d72938a68b8a10d3a5ee736d679","datavalue":{"value":{"entity-type":"item","numeric-id":3129826,"id":"Q3129826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d89c89f77dad3998240eee8cc5ff3800451875f7","datavalue":{"value":{"amount":"+0.92958194","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2497471$C556B03F-C2F1-4A3C-905B-4AE18B62A09C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"661a8ff5a777e84bd2146090831c809bdc64937c","datavalue":{"value":{"entity-type":"item","numeric-id":2816137,"id":"Q2816137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d5ed00b64d17d94d68df4d8e76692d9c9ec0cd0","datavalue":{"value":{"amount":"+0.9292687","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2497471$EB388B02-6955-4E7C-AB5F-6BF45FDDF201","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7749f130f53f6f727a764836c6a1e19a619e20de","datavalue":{"value":{"entity-type":"item","numeric-id":844210,"id":"Q844210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d711a2ae27d8c6bdf67f57c13f468840f5edbb4b","datavalue":{"value":{"amount":"+0.929104","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2497471$CE2D2CBF-3C1F-4B5E-B507-02763E333090","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95ba195262e4ab40390244431a1c289a13502154","datavalue":{"value":{"entity-type":"item","numeric-id":2350598,"id":"Q2350598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"554decbbebf5aa66664519a493ef0b74f966e5a7","datavalue":{"value":{"amount":"+0.92456007","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2497471$B0E62E38-9D9F-41DC-A91B-2D2318F20111","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4bef5bcdc8d4461813810a20a9b217e46557c8cd","datavalue":{"value":{"entity-type":"item","numeric-id":4581287,"id":"Q4581287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ba58b241e90eb0c0eceb46c6a899c1bd8883f6b","datavalue":{"value":{"amount":"+0.9215283","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2497471$E56EC735-6A67-429E-90C7-7941C098EC50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ac670e0af5df1348dabfb9656ccb29c19fb910f","datavalue":{"value":{"entity-type":"item","numeric-id":933674,"id":"Q933674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc5f122ea90058d5eb8dafc9b6e5987c31b7aa99","datavalue":{"value":{"amount":"+0.9195849","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2497471$F8741327-C52B-4F37-8962-C85A7C132820","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2497471","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2497471"}}}}}