{"entities":{"Q1386477":{"pageid":1397217,"ns":120,"title":"Item:Q1386477","lastrevid":68835402,"modified":"2026-04-13T02:23:33Z","type":"item","id":"Q1386477","labels":{"en":{"language":"en","value":"The number of dependent arcs in an acyclic orientation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1154635"}},"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":"Q1386477$05D26530-1E78-4BE3-9DD9-B503CAAE6FB7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"550553dd87b2f8f503b3ee2ba6f8041e1af551a9","datavalue":{"value":{"text":"The number of dependent arcs in an acyclic orientation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1386477$0C2DD961-5A3F-4185-A31D-4D6677934210","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3a88667a375d5a7557a5f5db549b5dd701778721","datavalue":{"value":"0901.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386477$ACE67559-EF8D-45BA-84BC-2C8931C96B63","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"211767d970c8c41b0c861a1ce10de3d1a1b687b8","datavalue":{"value":{"entity-type":"item","numeric-id":201977,"id":"Q201977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386477$A297399B-F317-4089-959C-2183376EF450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1200a2d2d33048b8518da57e6ed180fe561cbeab","datavalue":{"value":{"entity-type":"item","numeric-id":1385341,"id":"Q1385341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386477$490D8A77-2EAB-4A60-A072-5336ED690A2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4d4c73f0a1fcfa77f8c56f84fd9c0566fb0d581","datavalue":{"value":{"entity-type":"item","numeric-id":185079,"id":"Q185079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386477$6B8CD663-DCE3-42F6-957A-33AF1A3E536C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"af07d39ea0b7031bda891e71c6d4856a5cd292d6","datavalue":{"value":{"entity-type":"item","numeric-id":266824,"id":"Q266824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386477$72894C84-2432-460E-BC99-0289FF1AD71E","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":"Q1386477$8A13BA2E-13E3-47EE-92BD-2A44E6623D3D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e2bcebd569bbfb5b8b0063ba2286496f2af92031","datavalue":{"value":{"time":"+1998-08-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":"Q1386477$524BF51D-21A0-4181-BF61-877C6D546157","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"67f0634141176c54d40083fcdb5d73d7fe8a5f89","datavalue":{"value":"https://semanticscholar.org/paper/25e8dd91bae5215f220e490c4e3c4b981d49e0ea","type":"string"},"datatype":"url"},"type":"statement","id":"Q1386477$A7C29FCD-2E03-43E6-B8DC-7147E8AF77F6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a5abcfb554c2b157ea5d7be5e0499f44888d2ced","datavalue":{"value":"Let \\(G\\) be a graph with \\(n\\) nodes, \\(e\\) edges, chromatic number \\(\\chi\\), and girth \\(g\\). In an acyclic orientation of \\(G\\), an arc is dependent if its reversal creates a cycle. It is well known that if \\(\\chi< g\\), then \\(G\\) has an acylic orientation without dependent arcs. Edelman showed that if \\(G\\) is connected, then every acyclic orientation has at most \\(e- n+1\\) dependent arcs. We show that if \\(G\\) is connected and \\(\\chi< g\\), then \\(G\\) has an acyclic orientation with exactly \\(d\\) dependent arcs for all \\(d\\leq e-n+ 1\\). We also give bounds on the minimum number of dependent arcs in graphs with \\(\\chi\\geq g\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386477$DDCD283C-0B77-405C-89DC-0D3038508683","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386477$0B839F9B-F07A-4595-8B91-FAFCBE2F7A97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386477$FF893F04-B54E-4DD5-9E24-4180BBC604F4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7faa9993a41f980be2cb61f11eddac259d967962","datavalue":{"value":"1154635","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386477$7EECD767-B119-4BB2-B82B-19337A9DEBEC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386477$E7C25EC8-D293-4A40-B8DA-4E55ECB3FF45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd08082ecfb3b93b17c9a46ab514e0f78e6b2bec","datavalue":{"value":"acyclic orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386477$CBEF4689-3571-4D90-AB61-3C7B6978DCD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64b3aef55aef6d8c191ddd04cbaad4fd058d055c","datavalue":{"value":"dependent arcs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386477$3BDA5AE2-9912-4F09-85B1-33CA0059D696","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":"Q1386477$B94DF6C4-A9F5-4676-880D-AFFB44E1BE32","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"572e09e844a360d0ad55f0881d4f48750abd5797","datavalue":{"value":"W2014400460","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386477$B0F73BAA-7135-48DA-B722-11695B23927B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f39e69926d1ff50564509d93f46e54f3dcfb88e8","datavalue":{"value":{"entity-type":"item","numeric-id":580382,"id":"Q580382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386477$88E3D7C4-026F-40F6-BC69-9B3B47C9BA27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4216e3c93fc7c3ba5f60d5fa76fa9448cfa3dda","datavalue":{"value":{"entity-type":"item","numeric-id":1319079,"id":"Q1319079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386477$EF7C81B1-63A8-45AD-86A7-31C42A7503EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27b91fb34b309a1448e42736f924e3a5012ab649","datavalue":{"value":{"entity-type":"item","numeric-id":3253064,"id":"Q3253064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386477$69441B73-890B-4E9F-9E48-191D62F7EF3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fd7e20f7a8a5b57aaaa1397122dafb976668c5a","datavalue":{"value":{"entity-type":"item","numeric-id":5540284,"id":"Q5540284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386477$A3741625-FD55-479A-9EF4-F7BA7609F1FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34ada9500bcc818699dec7a40b5563f97b9191db","datavalue":{"value":{"entity-type":"item","numeric-id":1260043,"id":"Q1260043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386477$F5BFFE9E-4E84-47D4-9FF5-8E8340255312","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9e006f6f0eaa68f1180b803152ab2f45477d831","datavalue":{"value":{"entity-type":"item","numeric-id":4852554,"id":"Q4852554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386477$AD7AF7EF-E2EC-4925-B630-DD9E6A5FCC25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"521d541047569532dfe633e42547b0e6f42523ea","datavalue":{"value":{"entity-type":"item","numeric-id":1176731,"id":"Q1176731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386477$841FB90D-87B3-4CA6-80E3-EB38110299C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3139ed41572b735bd420bbcb7fccb9428d3554f2","datavalue":{"value":{"entity-type":"item","numeric-id":1842186,"id":"Q1842186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386477$E7B49022-899B-4CF8-9C15-B37E1B24F57D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"40cb2c32f213f3aaf89d00c929151f8f58bbc3be","datavalue":{"value":"10.1006/JCTB.1997.1769","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386477$EC51D4C7-EFE3-4080-8EB3-8BE9B6319100","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9250816ecd1d12ecab16348eb25010d73152f61","datavalue":{"value":{"entity-type":"item","numeric-id":967346,"id":"Q967346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2baaad81a6a1e00f371f022d3705fa75be3369d5","datavalue":{"value":{"amount":"+0.8331471085548401","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":"Q1386477$6A0513B1-DF00-45EA-84FD-8C8724E83138","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c4fa15dbd8427a82dcd03011d323a9043d4cd5c","datavalue":{"value":{"entity-type":"item","numeric-id":2851537,"id":"Q2851537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61df0a73f7fd5fe5f9bcd87f2ce82805f89e101f","datavalue":{"value":{"amount":"+0.8167749047279358","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":"Q1386477$5E083B7F-3B20-4A7B-A8CC-407615C21983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0cb204d7f476ebe577a98f49419024280c43a142","datavalue":{"value":{"entity-type":"item","numeric-id":2581566,"id":"Q2581566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b4587c0faa2b2cee3c7cd0fa9b8948b085d880b","datavalue":{"value":{"amount":"+0.8089065551757812","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":"Q1386477$B8EC6554-3F83-4345-A059-334129EC03BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e03a6cd08450d4e6bbd521983b829b2557e9698","datavalue":{"value":{"entity-type":"item","numeric-id":2823219,"id":"Q2823219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"499973dc4ec5a5f24d13a218d93042acf031e428","datavalue":{"value":{"amount":"+0.7957727909088135","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":"Q1386477$A1EDAA6C-4BD6-4B8C-969B-77E9A425756F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ea569544fb2c328cea9fb4319d0e8ed8db86e0a","datavalue":{"value":{"entity-type":"item","numeric-id":4898317,"id":"Q4898317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"570ff638f0e41b476c1c660d91a567b256a5304a","datavalue":{"value":{"amount":"+0.7949284911155701","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":"Q1386477$8D3FD16A-EEAA-49C7-885A-0AE8FF05368E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The number of dependent arcs in an acyclic orientation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_number_of_dependent_arcs_in_an_acyclic_orientation"}}}}}