{"entities":{"Q1297403":{"pageid":1308153,"ns":120,"title":"Item:Q1297403","lastrevid":46676649,"modified":"2025-12-25T09:28:56Z","type":"item","id":"Q1297403","labels":{"en":{"language":"en","value":"A bound for the game chromatic number of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1321769"}},"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":"Q1297403$28CA93D1-5E4D-4295-9A49-1BC772598A5F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fd4ed307d1eaca2af3afb6c8e95b7bb555ae896b","datavalue":{"value":{"text":"A bound for the game chromatic number of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1297403$BE2E6FB7-44A6-4F16-AA2B-6243911C8A02","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f7beb827cd02203df20e4520ad6d7d16c33a0952","datavalue":{"value":"0928.05022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297403$76CCB2D2-B69C-41FF-AC4A-70951DBFF167","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"67094b0d9853ef72a2ec81d4b21098622af17d0a","datavalue":{"value":"10.1016/S0012-365X(98)00197-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297403$5689D888-49E7-4786-9F8D-DF95FF1ED7F0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8ace0a192ca142725e852e4333f48601a1b730a3","datavalue":{"value":{"entity-type":"item","numeric-id":1297402,"id":"Q1297402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297403$5E65CAD2-6D27-45EC-B972-145E4C013A50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6b19b09c7519f38384d021f845694abb1cfab04","datavalue":{"value":{"entity-type":"item","numeric-id":168189,"id":"Q168189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297403$9727CA18-10D2-483E-9246-91BE898AFA03","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":"Q1297403$83F44854-5EEC-4F0D-98D6-5E825C9E6DAB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2f91e6392d7d983ceacbbbdfa34bd6021ee98113","datavalue":{"value":{"time":"+2000-01-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1297403$1541C503-CD34-4DEF-A606-84C4FE637E33","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"483904eeccb4f93d6ea77c0f061251d72c5cbe2c","datavalue":{"value":"The game chromatic number of a graph is the smallest size of a set of collors, where Alice has a winning strategy in the following game. Alternatingly, Alice and Bob select an uncolored vertex and give it a color, different from the colors of its neighbors. Alice wins if the entire graph has been colored; Bob wins if there is a vertex that cannot be colored.   The acyclic chromatic number of a graph is the minimum number of colors, needed to color the vertices such that no two adjacent vertices have the same color, and for any pair of colors, the vertices with that color induce a forest.   In this paper it is shown that if a graph has acyclic chromatic number \\(k\\), then it has game chromatic number at most \\(k(k+1)\\). From this, it follows that a planar graph has game chromatic number at most 30, a result later improved by Zhu with a different technique to 19. Also, bounds are obtained for the game chromatic number for graphs embeddable on a surface of bounded orientable genus, graphs of bounded treewidth, and series parallel graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297403$F8285EC8-930B-4208-A8B7-E980DC0E923E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297403$AAF78C5F-0179-4EC7-81C1-5F6CD03190B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297403$B4EC95A8-B1CF-4340-A317-3EEEDAE6845F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297403$9E3E7207-75CB-4D6E-AB77-03F4D4A1F0CE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f7f13773cb83c7212c0e8acdf56c5e49572936cf","datavalue":{"value":"1321769","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297403$603031D9-41C7-41AD-AC11-A5584008BAA8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a963503414bb31a41fdec1c5970580fc87536736","datavalue":{"value":"game chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297403$D2872676-0EF4-4D48-8C55-5F8EB72B91AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0356c2e27890491bf2eb295bab1472565bcd67b7","datavalue":{"value":"acyclic chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297403$57D517AE-BBD6-403A-897E-7D69D0AE060E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297403$EA14C427-7E71-49C1-86CF-CF2899E23199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"469d0b8ea86b9f7e9c590f45729834589d18a04b","datavalue":{"value":"orientable genus","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297403$F6B85700-8945-45CF-A27C-19950C8C8A6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d57d68ed777850433efcc3de197edd817953ef26","datavalue":{"value":"treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297403$6C6E37D6-E816-425F-A598-5549AC55B099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"298eb8c4afc734b0c7e4afaf8bf1c1109c202d48","datavalue":{"value":"series parallel graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297403$742411B6-F083-4EFA-A1C6-3107EBEAEF23","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eea1ea35de576c62b8101835521aa928ecd629a1","datavalue":{"value":{"entity-type":"item","numeric-id":242851,"id":"Q242851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297403$48D2D88B-602E-4EA0-B256-569EA1FD826D","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":"Q1297403$C1A45509-BAD6-4FC5-B76B-77E24D6E4420","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"68f023da32c0daad43fc50732d100a529f1a0d45","datavalue":{"value":{"entity-type":"item","numeric-id":4156455,"id":"Q4156455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297403$436B7FB8-0A70-4376-AFFA-58CDA6429C8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c04cd6dca3854d61d4454b442009254a6078a128","datavalue":{"value":{"entity-type":"item","numeric-id":4028100,"id":"Q4028100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297403$DD7A239E-58EF-47B2-A246-7EDFD61E1012","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":"Q1297403$5D86343A-58A6-48D5-B340-07C2D549E509","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":"Q1297403$0DE03EC3-6529-46CA-806D-C0AD9109BCF2","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":"Q1297403$143A9D61-0318-4C38-BDF0-DB80AC0FC67A","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":"Q1297403$7788B818-5676-44C5-89D1-18FE6AD02CA3","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":"Q1297403$E0B6F0BC-AF25-4A82-90F4-1ED56B959CE9","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":"Q1297403$2292F252-EF5E-4E29-BB5B-B62C38ECAED1","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":"Q1297403$8C26E963-259D-461E-BD5F-0A73576D1195","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f92eacc6f9d2252d3f6d43aa0905a3bb52d6a5f","datavalue":{"value":{"entity-type":"item","numeric-id":4256107,"id":"Q4256107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297403$3AD998CE-9393-49EE-A341-AA0F1C8CAE3C","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"8e87e6e08bf00408951fd92669d229e3f24cda61","datavalue":{"value":"Q126550987","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297403$A9F59F63-6BAD-4DD2-8EC2-B68FB49A0627","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf7ba4071a70319a317786133169353309e23745","datavalue":{"value":{"entity-type":"item","numeric-id":1305532,"id":"Q1305532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0241e8ee139d681520040c719d7a9d3ae8a45b40","datavalue":{"value":{"amount":"+0.8860663771629333","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":"Q1297403$4A2C857E-08EE-4635-A2DB-28481D215384","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4532f7e7f78fb5c13fdfa58dffc4099ae7524318","datavalue":{"value":{"entity-type":"item","numeric-id":4309985,"id":"Q4309985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a00f522ff0f3adc9e006c1c8334b640042b50cc","datavalue":{"value":{"amount":"+0.8696503043174744","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":"Q1297403$2DB86729-6C3C-484A-9703-C3B0054A179A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d948c9ce520323b93c01635d4ac55c39d005c63","datavalue":{"value":{"entity-type":"item","numeric-id":3138289,"id":"Q3138289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b16b301f1150c15d6a05d5ab9bc21e829813047","datavalue":{"value":{"amount":"+0.8626315593719482","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":"Q1297403$DDAA252F-492D-4C3B-87BA-431BCC584B4E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1297403","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1297403"}}}}}