{"entities":{"Q1305532":{"pageid":1316282,"ns":120,"title":"Item:Q1305532","lastrevid":68415936,"modified":"2026-04-12T23:33:46Z","type":"item","id":"Q1305532","labels":{"en":{"language":"en","value":"The game coloring number of planar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1346896"}},"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":"Q1305532$B288B387-4201-460C-9566-2367AD673680","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c3032f8c872c10026d32827c2216e9bd77db3144","datavalue":{"value":{"text":"The game coloring number of planar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1305532$55E241E0-F308-41C1-AB2C-65ED0A582012","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5af0488f72f28f8b99ac0f347e95d589604739d1","datavalue":{"value":"0933.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1305532$7752867C-6E68-40C3-AAD2-7969F9111D0B","rank":"normal"}],"P16":[{"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":"Q1305532$6C3286F4-BFF5-42C2-A6D3-C4CF14243F5D","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":"Q1305532$7211B6B0-1AAB-4F5C-858C-59DE8278F833","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"133f6ae6dfb800b668c32271be33f0f9ba6e88cf","datavalue":{"value":{"time":"+2000-04-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":"Q1305532$345C8BF5-67C0-4C3C-A12C-088D242417D8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"efa7c19c99dcbba84547695025fa1c61615d0980","datavalue":{"value":"The game chromatic number of a graph \\(G=(V, E)\\) is the minimum number of colors, such that Alice has a winning strategy in the following game: turnwise, Alice and Bob color an uncolored vertex \\(v\\) of \\(V\\) with a color, different from colors already assigned to the neighbors of \\(v\\). Alice wins when \\(G\\) is colored; Bob wins when there are vertices to which no color can be assigned. In the coloring game, Alice and Bob turnwise color a vertex of \\(G\\). The outcome of the game is \\(1+k\\), where \\(k\\) is the maximum number of colored neighbors of a vertex when it is colored. Alice tries to minimize the outcome, while Bob tries to maximize it. The minimum outcome when Alice plays perfectly is the game coloring number, which is an upper bound for the game chromatic number.   In this paper, it is shown that the game coloring number (and hence also the game chromatic number) of a planar graph is at most 19, improving upon an earlier bound of 30. This bound is obtained using the notion of light edges, a decomposition of the planar graph into subgraphs with special properties, and a detailed strategy for Alice. The paper also poses a number of central open questions in this area of research.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1305532$02E88CB8-F58E-4473-A91F-DC583F8861C9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1305532$D2BDC8AF-39AD-4DB0-ABBF-236BE79113F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1305532$1F4C759C-308B-429B-9F3B-2F007B3EF0DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1305532$D390D259-CB1A-4E9D-8716-C30B695D49EB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d6ec57f9ca400856771372746dfe768663804fa5","datavalue":{"value":"1346896","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1305532$7410AB26-C72D-4848-9C9D-C9E18973354A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a963503414bb31a41fdec1c5970580fc87536736","datavalue":{"value":"game chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1305532$F86E64D6-FC35-40B9-BE2F-048645BBE61E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7230d82cfb54344c915515262e04babcb2bfcc27","datavalue":{"value":"coloring game","type":"string"},"datatype":"string"},"type":"statement","id":"Q1305532$140E2BD2-DB53-42B4-BECE-37E77B953989","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b31c326a19f5847a998f3143391baccc4e991af","datavalue":{"value":"game coloring number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1305532$0BC51F6C-9BA0-4918-B2A2-916DFB54DB46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1305532$731693A2-CBB5-4398-8E72-350F945166EF","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":"Q1305532$DCF783E2-75DD-412A-A692-0DF570FB049B","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":"Q1305532$8E176026-6239-4D39-BB26-B38336A45D78","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":"Q1305532$D98B7D77-06AB-4EB5-8BD3-602F644D42FD","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":"Q1305532$E823A86C-A06A-43A0-B73D-8ECFB757A509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17ddc6d1a656129cbe2b0aa5f2ceffa8973d4ec4","datavalue":{"value":{"entity-type":"item","numeric-id":1173768,"id":"Q1173768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1305532$908C95C1-13FC-4178-8344-57628A762907","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":"Q1305532$6E674363-5AB3-4E0B-ADCE-B62CF9CB008E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecd4a7bb251d1b3331fe50d8f473ca0364dd5d9d","datavalue":{"value":{"entity-type":"item","numeric-id":4024455,"id":"Q4024455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1305532$1C7B34BE-3A12-438A-9E88-23221CA4135D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ae6f9719bcaef15a33f4b71446b58d4225bde22","datavalue":{"value":{"entity-type":"item","numeric-id":4321246,"id":"Q4321246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1305532$FC9725C9-94B4-426F-B255-25E6C126F687","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":"Q1305532$14641C24-EA4B-443B-ACF8-4D6ED69580CB","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":"Q1305532$BF463E7B-D31C-454C-8E21-E2D7CA396A28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e876ba4687a61332052a08dcc7eaabdefedd920e","datavalue":{"value":{"entity-type":"item","numeric-id":5560178,"id":"Q5560178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1305532$5596DDD8-3349-4C2B-84C2-1727D04E1236","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":"Q1305532$3492B25F-A2D9-4C8E-B15B-12036018EA7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddb209b5f842758c420a337fc7ccf411f373b50b","datavalue":{"value":{"entity-type":"item","numeric-id":2526108,"id":"Q2526108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1305532$2CD85717-B1B6-4B87-B284-9DDAFF17A7A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f855246caf01e7d423da5ddcd02591be6660a7f0","datavalue":{"value":{"entity-type":"item","numeric-id":4857375,"id":"Q4857375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1305532$5BA424AE-9CBE-4C13-AD47-22E1ABBD3C60","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":"Q1305532$FBF259FD-8813-4B4A-B1FB-FA8506427E84","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":"Q1305532$BEF35714-20E0-41D4-92EC-745BF2D7E757","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9457bbf299deabc8d481a667398bd8f4df94f43e","datavalue":{"value":{"entity-type":"item","numeric-id":5344765,"id":"Q5344765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1305532$C56F391A-BCCC-4C91-9C37-3206189517BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef1e280ff313784cce95cf1dc6e1b139af0e3310","datavalue":{"value":{"entity-type":"item","numeric-id":5599569,"id":"Q5599569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1305532$6CD94D2C-A221-4F85-BAA5-7EE00567FAA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79f40f6cac0c780a9b93fef04ad01fbee5da55dc","datavalue":{"value":{"entity-type":"item","numeric-id":5731396,"id":"Q5731396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1305532$C8DDB372-FFB0-4F42-AA8F-81794425E0F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46c8a1be5e3753dd926687b6fc07f22f3de1ed22","datavalue":{"value":{"entity-type":"item","numeric-id":4875686,"id":"Q4875686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1305532$C8946658-9F93-444B-81C1-DF91F3CF7CA5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f38db4b4d56e930e2a95bec12794a1724062ad09","datavalue":{"value":{"entity-type":"item","numeric-id":1297403,"id":"Q1297403"},"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":"Q1305532$A174C182-3830-4256-B7B3-0BEF6655B160","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":"22a4b77271d78ec6449b21ec23511f8bede06879","datavalue":{"value":{"amount":"+0.8787631988525391","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":"Q1305532$C14B9FF1-B237-4351-8366-E80836DA2CFF","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":"6868ec8cac8b75e31728a212d228f23f2a8c7c38","datavalue":{"value":{"amount":"+0.8676679134368896","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":"Q1305532$09AAAF67-4096-463A-9383-442A4DE7A19C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The game coloring number of planar graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_game_coloring_number_of_planar_graphs"}}}}}