{"entities":{"Q1025913":{"pageid":1027761,"ns":120,"title":"Item:Q1025913","lastrevid":66569361,"modified":"2026-04-12T11:00:24Z","type":"item","id":"Q1025913","labels":{"en":{"language":"en","value":"Planar graphs without 5-cycles or without 6-cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5569044"}},"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":"Q1025913$4B49787F-5F89-45E8-84F9-88003138A729","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cce4422f8dfc652c8e51e514e17e4ec11cf0df06","datavalue":{"value":{"text":"Planar graphs without 5-cycles or without 6-cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1025913$45E7FED4-005D-482C-AA76-E96AB7BC1F33","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a0bd0d79ffcb59db587d7234951f8ac97e50a0ef","datavalue":{"value":"1186.05043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025913$82C2CBE1-18B1-469A-A8AD-1FFB35E94867","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7f5c6ba829a24d5fe0050a6d775ae0006b589b8e","datavalue":{"value":{"entity-type":"item","numeric-id":949133,"id":"Q949133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$91A3F5DA-B5E9-463D-BFFA-AC1663E492A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"433c7c5c694bc5e513c30ec134f1dc83c63e359e","datavalue":{"value":{"entity-type":"item","numeric-id":592984,"id":"Q592984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$C84E572F-1E1F-483D-BDC3-767943203517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"48b880f876593afdc72edadad8338de5abfe7496","datavalue":{"value":{"entity-type":"item","numeric-id":6546865,"id":"Q6546865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$22845A23-DA69-4698-90B2-FB884CED56E5","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":"Q1025913$C984259D-C05B-4256-B0F7-8FC2BA3A2581","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f66a2f08b182488ffaf8c1a4c74cdffeb2d3409b","datavalue":{"value":{"time":"+2009-06-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1025913$6DF96B48-ECD0-4049-A834-449110280416","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ba1dab1a6e4ef69b0b245b4d93cea3d4994d6e3a","datavalue":{"value":"Let \\(G\\) be a graph without 5-cycles or 6-cycles. The authors show that there is either an edge \\(uv\\) with \\(\\deg(u) + \\deg(v) \\leq 9\\), or a cycle of even length such that every other vertex is of degree 2.  The list-edge-chromatic number is the smallest \\(k\\) such that if each edge is assigned a set of \\(k\\) colors, there is always an edge-coloring using colors from each edge's list such that adjacent edges receive distinct colors. The list-total-chromatic number is the smallest \\(k\\) such that if each vertex and each edge is assigned a set of \\(k\\) colors, there is always a coloring of the edges and vertices from each's list such that adjacent or incident elements receive distinct colors. The linear \\(k\\)-arboricity of a graph is the smallest \\(m\\) such that the edges of \\(G\\) can be partitioned into \\(m\\) parts, each part having components that are paths of length at most \\(k\\).  The authors use the first result to show {\\parindent=7mm \\begin{itemize}\\item[(1)]the linear 2-arboricity of \\(G\\) is at most \\(\\lceil (\\Delta(G)+1)/2\\rceil + 6\\),  \\item[(2)]the list-total-chromatic number is \\(\\Delta(G)+1\\) if \\(\\Delta(G) \\geq 8\\), and  \\item[(3)]The list-edge-chromatic number is \\(\\Delta(G)\\) if \\(\\Delta(G) \\geq 8\\).   \\end{itemize}}  The advantage of considering graphs without cycles of length 5 or 6 is to restrict how cycles of length 3 and 4 can intersect. This allows the authors to use discharging methods as if the graph were of large girth.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025913$F7D93DDA-5B15-4AE1-8AB9-D56E258C3014","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":"Q1025913$7018C13D-2AF8-423F-B0EE-66FECB1D7B1B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025913$DFC6A065-5459-433B-AE0B-8A7A21D8FBF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025913$5219A33B-954C-45D0-88AB-2A4A1ECBC458","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025913$DEE2F369-2FBE-4EEF-8B8F-4804BAAF2FB8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6e4b91188f3674dd59846bdb244f5307e520f9fe","datavalue":{"value":"5569044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025913$531D2C87-E912-44AF-966C-4AACC915250C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c856145ef6cf7ef96d1f0755055e2ec6f5396f57","datavalue":{"value":"planarity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025913$5F96847F-2CBB-4306-92C8-9F4F0894CB81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0286134cd56ebaa48cb73a6a7c2e961fe7af2df2","datavalue":{"value":"discharging","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025913$6E6BF910-6289-4CB7-8E4B-8CB78F91D2EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"55ad6a03768bc606211c873247c9842c07b22d46","datavalue":{"value":"list colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025913$1F96B013-2D9F-4E05-A7B9-3460E380C6FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"33d42ddf4e1ea41f5d8846555ec9a668fbb0211f","datavalue":{"value":"arboricity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025913$A9ED5563-ECB1-42F9-838A-AF3D2EFCC095","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b459601159e0391e8bad336a967b62e9af12d86b","datavalue":{"value":"list edge chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025913$9679651A-81B4-47FC-B4CE-0CCA9F178D22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1caf928c8897971df2f255ba80517a2494196510","datavalue":{"value":"list total chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025913$11B226F1-DDAD-4543-A4D6-78D094FA4BEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c749e9ee880844f1c70f4c704f6c39e197fc56ab","datavalue":{"value":"linear k-arboricity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025913$FF93E2D7-748F-4A0F-9CD1-0C179192D816","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":"Q1025913$D364005F-84BC-47DE-9F3F-8210DE4507B1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bb5cd98f4eaa9bace39527b3a27162d588f2adfc","datavalue":{"value":"https://doi.org/10.1016/j.disc.2008.07.033","type":"string"},"datatype":"url"},"type":"statement","id":"Q1025913$0291C97F-393D-48DC-ADD5-075E2C3C303A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"730ca0b7ec69dd411a10dc259f99350a50fccfee","datavalue":{"value":"W2088603101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025913$4CC4DF3A-474F-40B8-8345-DC4C46F29F48","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"9524aa69d596716024fa01c3b02e72db43798dae","datavalue":{"value":"Q62838274","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025913$5A9D7F71-6CC3-4818-B892-61A1C53E15F6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"19aafb0d768a31243436a77bcbbe4167aa96c8c1","datavalue":{"value":{"entity-type":"item","numeric-id":4222072,"id":"Q4222072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$7318B26B-D3EB-4BF1-915C-40A5266EE531","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38b451f059814158c911074afe693b201879c742","datavalue":{"value":{"entity-type":"item","numeric-id":761470,"id":"Q761470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$8F1E6D1F-09FF-48B2-8B98-06A0C8248FD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$3F7F95F0-BC92-45F3-A22A-2D8382E92C0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb8b23be685b19bdd0313eaaa79ce5140147fe55","datavalue":{"value":{"entity-type":"item","numeric-id":1366604,"id":"Q1366604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$08847913-61EC-45FE-8BB3-9DA84D217582","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7806caea286c16e9c9b5828d442a159f76e8cbcf","datavalue":{"value":{"entity-type":"item","numeric-id":1301997,"id":"Q1301997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$05D0688C-B819-4634-BBBA-97C652508D47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c55a118a9a06d9106a2dfee27a83ef0413537c74","datavalue":{"value":{"entity-type":"item","numeric-id":1570841,"id":"Q1570841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$F8C99A0C-1C93-4F8D-87E8-C6F155BC330F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65855013b74e681f0bb792db199c877755db1625","datavalue":{"value":{"entity-type":"item","numeric-id":4017192,"id":"Q4017192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$90221E8F-60A2-4BC2-9C0F-CDD7BFA8F4A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2859163c640147e679dc033f187b18a1e0d4cd8d","datavalue":{"value":{"entity-type":"item","numeric-id":4326214,"id":"Q4326214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$160C5BAF-6F37-4640-BF21-EA615C3B74DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa05da9d1b31047f36acfbf3fc6eb421f3b733ed","datavalue":{"value":{"entity-type":"item","numeric-id":1164649,"id":"Q1164649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$8B163A94-07C4-41A6-AF12-E53A9939E4A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"006b0fec402dd081a79466b39a53a39af7379296","datavalue":{"value":{"entity-type":"item","numeric-id":861265,"id":"Q861265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$159EEA56-9E6F-4983-A3C8-7A681F4C582A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e17b27dea6e8ef7f0fed8cf092cb4dc3f3602e9","datavalue":{"value":{"entity-type":"item","numeric-id":1356680,"id":"Q1356680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$94DB7392-D1CD-4337-B6C0-341F19743949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab8352af838542571ad6dad6e728d58c2d6d01e6","datavalue":{"value":{"entity-type":"item","numeric-id":4212879,"id":"Q4212879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$8289C18A-A8AD-4BCD-9D4C-0CC585CA512F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4377d5aef1b1539d22acb6a15e1e0b06369fb31f","datavalue":{"value":{"entity-type":"item","numeric-id":1401562,"id":"Q1401562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$D1F13FC3-1425-447E-8CFC-2EBFCBC999F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80eb4ddbe5ccd86e2620db99517a3596f46e6d80","datavalue":{"value":{"entity-type":"item","numeric-id":3415464,"id":"Q3415464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$E3A17DD8-929C-40A4-A359-EED8FD3E75BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d121cdeb1c638d1e652d84e6b13b6dcfaac9d2b3","datavalue":{"value":{"entity-type":"item","numeric-id":1306426,"id":"Q1306426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025913$0026068C-7198-4107-8A8A-600860E08343","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"643a9a968a36c7ad209c82d6b5d6208b63ef270e","datavalue":{"value":"10.1016/J.DISC.2008.07.033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025913$657A221F-1082-4AF6-940B-6C11D3BE4302","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9af4622991e35a1cdbe9b88c66c99ef3d178f73f","datavalue":{"value":{"entity-type":"item","numeric-id":5497525,"id":"Q5497525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8bb05ceb9f52373e5d4bf2720782820bee7a800","datavalue":{"value":{"amount":"+0.9032033681869508","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":"Q1025913$33D60BF8-A6E2-4A20-97A4-E01CB0524859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1241bb16e2a871cc8daae96721f7626d4f873985","datavalue":{"value":{"entity-type":"item","numeric-id":3115072,"id":"Q3115072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"209881d4a9104ee0f4bceee30cb57e6d7b392bb0","datavalue":{"value":{"amount":"+0.870888352394104","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":"Q1025913$15F00BCB-BE3C-4B77-831E-950B50EBBF7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7ce633927bec700c0d2c919fb25f49b8e08802f","datavalue":{"value":{"entity-type":"item","numeric-id":5206582,"id":"Q5206582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b2360f9cd5a2743f93d7f30798c11a659e5d299","datavalue":{"value":{"amount":"+0.868798017501831","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":"Q1025913$95FEC122-40A9-431D-8C74-11044CF010CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ad3e8b59e2f7d54427cd0d6de2b7978666fd46c","datavalue":{"value":{"entity-type":"item","numeric-id":975488,"id":"Q975488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec8119ae66f96ec4989af0ebb257e9a27ea434fa","datavalue":{"value":{"amount":"+0.8686627745628357","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":"Q1025913$469B2A0B-BD6C-4083-AB57-88A12E5D99D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"330ccbc3aeffe2a2efd8095c9ab7faa80dfff557","datavalue":{"value":{"entity-type":"item","numeric-id":3386158,"id":"Q3386158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9aafbd9e8f48c33136ca7c2ac72b0c0a176bbc71","datavalue":{"value":{"amount":"+0.8657003045082092","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":"Q1025913$3F6FD68F-35B1-42AD-A8A9-A07D52C7F89D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Planar graphs without 5-cycles or without 6-cycles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Planar_graphs_without_5-cycles_or_without_6-cycles"}}}}}