{"entities":{"Q1978502":{"pageid":1989244,"ns":120,"title":"Item:Q1978502","lastrevid":43460113,"modified":"2025-07-26T01:46:46Z","type":"item","id":"Q1978502","labels":{"en":{"language":"en","value":"Efficient algorithms for acyclic colorings of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1454282"}},"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":"Q1978502$53C28E22-2550-4229-9D19-0103FA032E68","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e14fcf50373f4875ce636b8f0af4597946baeb11","datavalue":{"value":{"text":"Efficient algorithms for acyclic colorings of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1978502$7451DF66-71F5-43A0-8D1C-90287FF09ADB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e44de2f48396e8b2d3f402d2e7524f1e95d10efe","datavalue":{"value":"0941.68096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978502$0E5B61A4-7A4A-4221-9697-7146B8C731D1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9f012546b5cf6c36645e38c553b454668135c430","datavalue":{"value":"10.1016/S0304-3975(97)00254-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978502$013267D5-6604-49BC-B346-BF7CA0046FB4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978502$47C395FC-99BB-4ED9-B19E-67F22D9F890E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978502$20F28335-2DA3-4EB0-8139-C38E310B0DA4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cea4e04940bd3504f3c0f2b605e025bc106fb722","datavalue":{"value":{"time":"+2000-06-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":"Q1978502$BDCC1977-EA57-428B-BA01-139B138B3407","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f5d7195a1906db9f8888453da373ba1d0502680c","datavalue":{"value":"An acyclic \\(k\\)-coloring of a graph \\(G\\) is a coloring of the vertices of \\(G\\) with at most \\(k\\) colors such that each color class induces an acyclic subgraph. The vertex arboricity \\(a(G)\\) of \\(G\\) is the minimum number \\(k\\) for which \\(G\\) has an acyclic \\(k\\)-coloring. Although the problem of computing \\(a(G)\\) is NP-hard, \\(\\rho(G)=1+\\lfloor(\\max\\delta(G'))/2\\rfloor\\) is known to be a good upper bound on \\(a(G)\\), where the maximum is taken over all induced subgraphs \\(G'\\) of \\(G\\) and \\(\\delta(G')\\) is the minimum degree of \\(G'\\). In this paper, we present the first linear-time algorithm for acyclic \\(\\rho(G)\\)-colorings. We also give a sufficient condition under which an NC algorithm exists for acyclic \\(\\rho(G)\\)-colorings. Using this condition, we obtain the first NC algorithm for acyclic \\(\\rho(G)\\)-colorings of graphs without a \\(K_{3,3}\\) (or \\(K_{5})\\) minor.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978502$1B5E5CF5-5324-433B-8066-E7BDD117D932","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978502$8501A7F2-65E7-4230-AC13-A1A54C43C30D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978502$6E20FF45-60B2-4A89-9344-9A2A4031BFA1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f064b8e9648ca05e1c31d9d668d9aa3d636e95d4","datavalue":{"value":"1454282","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978502$7EACB8E7-9499-4900-BEC0-B1857B9672AF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bb31798a25b0a3bb760ee440afa37d4784956b94","datavalue":{"value":"vertex arboricity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978502$EE241DDD-4D45-4003-9E1C-9CD6D695C2C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc478e34e6f14d65c1c770358f7b3ce7867f7d70","datavalue":{"value":"acyclic colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978502$25536C5C-15FB-4F2C-9E42-9E07930DD6A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978502$AB2F91F7-374A-4C88-9871-2A3AA1F391D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d3fc3f306278971b47588c54be6220243123d7e","datavalue":{"value":"sparse graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978502$9583D4A0-FA22-4597-BF6F-9338D13FAFD3","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":"Q1978502$72F63ADE-58B1-44BB-BED0-8B0140E04B4E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"491950cd634035e7fd95f4062271456f77492b49","datavalue":{"value":{"entity-type":"item","numeric-id":1062457,"id":"Q1062457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978502$EC579713-EB99-4938-AC86-D64955FAA3A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1962393e4cd9abd4f57d9d10b458d7bff499cd02","datavalue":{"value":{"entity-type":"item","numeric-id":5565641,"id":"Q5565641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978502$0049AE23-9A2F-4300-92A0-BA36A421565C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8233d277b3ded6133706ab325d38fe3bb56ae553","datavalue":{"value":{"entity-type":"item","numeric-id":2529589,"id":"Q2529589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978502$D14F1470-A013-4299-84B0-E137C7782B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bfc92546771c46bde171d7700a1e8accf58e7d3","datavalue":{"value":{"entity-type":"item","numeric-id":1923610,"id":"Q1923610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978502$177DB551-5BEA-4E1A-91B3-325927FF05C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d158cc3aa4f838cb96a6d00c9cb7a42742066354","datavalue":{"value":{"entity-type":"item","numeric-id":4202214,"id":"Q4202214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978502$C4E34CE6-CC4D-4F0D-897F-BDBCA9708185","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978502$898BC020-9B0E-4D59-A467-265BE0C37990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0705dba2acd9dac438df125217084631fd09541e","datavalue":{"value":{"entity-type":"item","numeric-id":5905418,"id":"Q5905418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978502$3034030C-0045-4454-8960-CD95D0D8B3FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b27564425cbc0f4a9eb7c83ae808997d7c47295","datavalue":{"value":{"entity-type":"item","numeric-id":808289,"id":"Q808289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978502$BEA1C306-E122-4C16-813F-0CE08A83702B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"739368edec33eedf3cce70386e0869ee3fa9e16e","datavalue":{"value":{"entity-type":"item","numeric-id":4763420,"id":"Q4763420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978502$B0CD379C-2FC9-4EAC-973C-D5F41586502F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"547f52ee14fb7124fc2c5a79a6ec62ef9700664f","datavalue":{"value":{"entity-type":"item","numeric-id":2956672,"id":"Q2956672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978502$B955A532-9B8A-4225-9AD9-6F03F30C521C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a9db4a207e2ab9eef002ed1bcd0688887d186bc","datavalue":{"value":{"entity-type":"item","numeric-id":3957960,"id":"Q3957960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978502$54EED5F1-2E7A-4FCC-A306-ABFB3AEB7498","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c5477e08259683f4f1214eab272881c214067b5","datavalue":{"value":{"entity-type":"item","numeric-id":3694710,"id":"Q3694710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978502$528E0310-3858-42E4-9D8F-9333A5B0B34A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53931acda4d1de6fffc8c785b472a64b77dbbda9","datavalue":{"value":{"entity-type":"item","numeric-id":5402565,"id":"Q5402565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978502$2653DA02-076C-49A5-84CB-C7A1704CB9E3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d20705e7bac255a4f0c6130ac3ed476a54603e6","datavalue":{"value":{"entity-type":"item","numeric-id":1348909,"id":"Q1348909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eea8bc061ac4a4f52e688ad84bca234ea8af7806","datavalue":{"value":{"amount":"+0.9442053","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":"Q1978502$86E03187-A93F-4D13-82AE-D0202B7608D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38c5cf4ef68a885a55b77319750e887889fd593e","datavalue":{"value":{"entity-type":"item","numeric-id":4931915,"id":"Q4931915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0626e019f10cd27d1be09e566c10855855d0d5da","datavalue":{"value":{"amount":"+0.922404","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":"Q1978502$40AACDF2-97D2-4B53-95C6-43B272AF1431","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7ab5962d131ddfc88eecdde898ba4de44929a3d","datavalue":{"value":{"entity-type":"item","numeric-id":3977081,"id":"Q3977081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c901382035544296e23571df1975e001e4611f57","datavalue":{"value":{"amount":"+0.9208426","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":"Q1978502$6A9EDBCB-B125-4ECF-B14D-50C1466B9BF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f716a298f7334674374adfc3de964fec70847ab6","datavalue":{"value":{"entity-type":"item","numeric-id":4009325,"id":"Q4009325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"489fc5c194d7fb1d104893dd21df310149dafe91","datavalue":{"value":{"amount":"+0.91063195","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":"Q1978502$5F91EDD9-0486-48FB-A584-675EC8FF71E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b26591057fae4a9aaa8745156dfbae88a847d32","datavalue":{"value":{"entity-type":"item","numeric-id":5063668,"id":"Q5063668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b07ff1944dfe80f1e5b1d22e80d11dc3ee8be231","datavalue":{"value":{"amount":"+0.9104963","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":"Q1978502$C061DD52-EBAE-4F52-AF12-B0FFFA57AF64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6cad9af57650c90f3ef8175e8dbc64baabf1c6f","datavalue":{"value":{"entity-type":"item","numeric-id":3004663,"id":"Q3004663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41e2119a28991f2a327261b2329090f57cfe6918","datavalue":{"value":{"amount":"+0.90938574","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":"Q1978502$49CF15DC-5FBD-4587-80D4-80CD8C4D885F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b50edc7369e14042c2adfbec4c82057cdec1f3a","datavalue":{"value":{"entity-type":"item","numeric-id":2440127,"id":"Q2440127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94c195a350203b3201ecff11fd4746029265812f","datavalue":{"value":{"amount":"+0.9067687","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":"Q1978502$54C1ED10-DC35-42BD-847B-B085397CF9CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b5f65a18b69f8638c2220c2d1c6ccb7c34b685e","datavalue":{"value":{"entity-type":"item","numeric-id":5687263,"id":"Q5687263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b6f6549796004a4d982349b308e7f296df3721d","datavalue":{"value":{"amount":"+0.9061903","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":"Q1978502$BBC07994-8148-41F4-9ED9-E50BAA6A978B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f89387e37fb607909ad2f3f1f9a1fd28927e38be","datavalue":{"value":{"entity-type":"item","numeric-id":2746208,"id":"Q2746208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d00316dd3245e445d326bebf36e8c99a1d4d4f18","datavalue":{"value":{"amount":"+0.90612406","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":"Q1978502$0DE37587-44AF-49EF-98B2-5E8DD8A95CD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4232355a5c9d37faf6bf3e16fbd35f82bf9adeb4","datavalue":{"value":{"entity-type":"item","numeric-id":3424889,"id":"Q3424889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"761b9ae88fa5c3084197358c2d0d2c58d9e1b954","datavalue":{"value":{"amount":"+0.9057524","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":"Q1978502$22AAD248-E2CB-4293-B4DC-BE50BD1093C3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1978502","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1978502"}}}}}