{"entities":{"Q2488942":{"pageid":2499685,"ns":120,"title":"Item:Q2488942","lastrevid":55850026,"modified":"2026-02-20T11:58:41Z","type":"item","id":"Q2488942","labels":{"en":{"language":"en","value":"Weak acyclic coloring and asymmetric coloring games"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5023280"}},"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":"Q2488942$AF4B8B42-6EFA-44FE-9217-816BBFB0AF43","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2d69c94f23f3d0ed6d93944830cd8de06158b7b6","datavalue":{"value":{"text":"Weak acyclic coloring and asymmetric coloring games","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2488942$A73A284A-6CE6-41B3-9E5C-CD4A6EF34A3C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a776586db71cff9639937fe8f4ad69451326b666","datavalue":{"value":"1091.05025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488942$029EF505-3DB2-46CD-BD21-28A638C274BE","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":"Q2488942$CE739308-F9D2-4D53-A54B-FE21115391AE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4c5f8875e456847c1a3ce95e32c0a4e149a6838e","datavalue":{"value":{"time":"+2006-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2488942$DDF5D04A-2EFC-4984-8B39-0B7364F199B1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"154465d670af2778157fba3694eb715dac5b9856","datavalue":{"value":"From the author's abstract: We introduce the notion of weak acyclic coloring of a graph. This is a relaxation of the usual notion of acyclic coloring which is often sufficient for applications. We then use this concept to analyze the \\((a,b)\\)-coloring game. This game is played on a finite graph \\(G\\) using a set of colors \\(X\\), by two players Alice and Bob with Alice playing first. On each turn Alice (Bob) chooses \\(a\\) (\\(b\\)) uncolored vertices and properly colors them with colors from \\(X\\). Alice wins if the players eventually create a proper coloring of \\(G\\); otherwise Bob wins when one of the players has no legal move. The \\((a,b)\\)-game chromatic number of \\(G\\), denoted \\((a,b)\\)-\\(\\chi_g(G)\\), is the least integer \\(t\\) such that Alice has a winning strategy when the game is played on \\(G\\) using \\(t\\) colors. We show that if the weak acyclic chromatic number of \\(G\\) is at most \\(k\\), then \\((2,1)\\)-\\(\\chi_g(G) \\leq (k^2 + 3k)/2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2488942$014849F7-B7D4-44E5-B896-17FDF15394DB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488942$1CDE9FE7-D101-4B49-A92A-01790D2596DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488942$58EC409A-3603-498D-A626-7E096CED900E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fb202c7bb7517ed47f6c078900715fecd3e11134","datavalue":{"value":"5023280","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488942$FF66CEE8-AB0C-48C1-8373-E37729E79919","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a963503414bb31a41fdec1c5970580fc87536736","datavalue":{"value":"game chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2488942$1F3A59D9-3898-4B9B-B4DD-A70DCA343C11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0356c2e27890491bf2eb295bab1472565bcd67b7","datavalue":{"value":"acyclic chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2488942$772B844E-AD95-41B5-B699-D7771765343D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e8e4763e432b6ffd9ef1ff20256862696bdf24ca","datavalue":{"value":{"entity-type":"item","numeric-id":555495,"id":"Q555495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$51AAB89E-E43E-48EB-B535-C3E08C32F1CB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b687a818ec58a93e77f94a71ec71ff4e2750b160","datavalue":{"value":{"entity-type":"item","numeric-id":592090,"id":"Q592090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$B31DA162-B878-443B-9A2D-67B13B51FA6D","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":"Q2488942$58B91A70-A1E1-4F95-861C-0FB303613EB8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"760fd3593d2a369a8da400811fa00ead0838010d","datavalue":{"value":"https://doi.org/10.1016/j.disc.2004.07.042","type":"string"},"datatype":"url"},"type":"statement","id":"Q2488942$3C5EAE7B-C1A9-46F3-8A8D-B9B098EA9B00","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c1c897ddc3c550309db0dcc05d90b344f743db15","datavalue":{"value":"W2092186407","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488942$3A5AD736-1CCC-48A0-8448-10FF0ED2E412","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2c1115e87dc51532b4feca2a675e0421662ac53","datavalue":{"value":{"entity-type":"item","numeric-id":1883636,"id":"Q1883636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$AC83FA62-B0D1-4899-A1AB-906FD41F4F20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"417e3e4270539efa5622bd510a126741665c19b7","datavalue":{"value":{"entity-type":"item","numeric-id":3988839,"id":"Q3988839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$B734436D-4C3B-48AA-8A49-027C1BF2A13B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f92dd856ac6e85d46c013684d1de479b1f38df9f","datavalue":{"value":{"entity-type":"item","numeric-id":1257487,"id":"Q1257487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$E8242732-ADA4-4C2F-BED4-D1A173850983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"941517d17c41c64f7b62f7eb9b2b332972f75dfc","datavalue":{"value":{"entity-type":"item","numeric-id":1297403,"id":"Q1297403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$37D98F76-C0A8-4F09-9856-5284D0DEBA19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694ee32736d8cf72f7a59d5ca258e6998a092fe2","datavalue":{"value":{"entity-type":"item","numeric-id":4201568,"id":"Q4201568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$689767EE-5B81-451F-A6C2-BCF68AFA4C93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61b5c47efe9ffc3dd4e3e9de3dd638c26801d78a","datavalue":{"value":{"entity-type":"item","numeric-id":5921616,"id":"Q5921616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$2E7A1799-62FE-4420-B3BE-9F1F8012C4E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57416264e564fe89b8672fa62df1899ad726ddc6","datavalue":{"value":{"entity-type":"item","numeric-id":1569067,"id":"Q1569067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$398CF5C8-BF74-4152-B705-2D2DD04F4D6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c8906cb2457240c0ae99288f65f2901613300b1","datavalue":{"value":{"entity-type":"item","numeric-id":4667798,"id":"Q4667798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$45769E2C-674E-41CC-882C-E6507EA55E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb7340c7e4bad066830d41cd30e631c015cc0e46","datavalue":{"value":{"entity-type":"item","numeric-id":4309985,"id":"Q4309985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$8D154F5C-B9D0-4D90-A3EC-6768A4EF8ED4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d53f3f80a4b9e159a15da92402633409071d17c","datavalue":{"value":{"entity-type":"item","numeric-id":5942566,"id":"Q5942566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$00F0276F-6533-49CD-B84A-5D96B6C78E87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d77ae356f89e295aa688367e7e2a1fb17f4b14d","datavalue":{"value":{"entity-type":"item","numeric-id":1396657,"id":"Q1396657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$CF7688F5-2CED-4735-9F2A-145BDCD3A54C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca211d12a54bef7ee54f54df8169c7e2b38e90f1","datavalue":{"value":{"entity-type":"item","numeric-id":5942568,"id":"Q5942568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$12EEEBCB-E8F2-4163-BA8C-22199E576B7E","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":"Q2488942$81D462C1-4C7E-4F2A-8602-349B21E16B6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b089caee1b8a892f778b339ad99a85f1bcb7f6c","datavalue":{"value":{"entity-type":"item","numeric-id":1305532,"id":"Q1305532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$48C22D8C-7E77-4B79-904B-48A95161E91C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"140390c19d1575566ae264cd7e84a3d158fc1aa0","datavalue":{"value":{"entity-type":"item","numeric-id":1974537,"id":"Q1974537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$E8B1E416-700E-45C4-98A7-B67EEC1E634C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d9134334b3799f11cac5c5b734a7df67539d640","datavalue":{"value":{"entity-type":"item","numeric-id":2464148,"id":"Q2464148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488942$1320D37E-EFDA-44F0-B6E1-6598069BD2C6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"667e4c5ed5cb7dc9fee45d30464401eaeb5378a1","datavalue":{"value":"10.1016/J.DISC.2004.07.042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488942$86F025CD-11B9-465D-9CC4-BE1EBC15B692","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbdec73507bcfd6fcb11cf5fc81733d654822669","datavalue":{"value":{"entity-type":"item","numeric-id":4667798,"id":"Q4667798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c22b080aea89107b9b1eb2b77a9572024db5a84","datavalue":{"value":{"amount":"+0.8656384348869324","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":"Q2488942$63B0454D-7B27-44C4-8A14-B7C3EAFAD869","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a89eeab1ccae16191254f63284514352e5a0e710","datavalue":{"value":{"entity-type":"item","numeric-id":1011775,"id":"Q1011775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f57792f6e4206c6000fc337ff9d3016744f22129","datavalue":{"value":{"amount":"+0.8330025672912598","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":"Q2488942$64A6C4C3-71AD-46A7-B837-5DC7E2EFAEF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25a8cf76fd7a1c8c9184bf84ecb7d07f3a8dd10f","datavalue":{"value":{"entity-type":"item","numeric-id":1025957,"id":"Q1025957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b5849bddeb32dad39c60c6bac584cf54f6d48de","datavalue":{"value":{"amount":"+0.8212257027626038","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":"Q2488942$697D5576-45AB-4DE6-B2BB-0EFBB7B2E451","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea0f3738cc54035c7c796c7f41a1c22eef8fefc3","datavalue":{"value":{"entity-type":"item","numeric-id":1045076,"id":"Q1045076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d9733dd8d7178553f4ba66bd08be6086cc55133","datavalue":{"value":{"amount":"+0.8064128160476685","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":"Q2488942$F62DE816-5C91-4832-AC4F-30568E18FC98","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2488942","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2488942"}}}}}