{"entities":{"Q1715067":{"pageid":1725808,"ns":120,"title":"Item:Q1715067","lastrevid":72218868,"modified":"2026-04-14T03:24:41Z","type":"item","id":"Q1715067","labels":{"en":{"language":"en","value":"Edge lower bounds for list critical graphs, via discharging"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7011203"}},"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":"Q1715067$1C6966E4-233B-43D6-BB41-4161AABEBA85","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cd4a19df255b66b49eb85a0ae63301475df2ce09","datavalue":{"value":{"text":"Edge lower bounds for list critical graphs, via discharging","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1715067$39485187-3C1C-4DB5-824C-90C09E8F4D3B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8bd23bf85ad26e638c76d59feaea4ab147834e23","datavalue":{"value":"1424.05081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715067$FDA06BBD-3823-46DA-8F86-6998EEBA83A9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae41f04ca594ca85b65fe9b038c9fd67cd961e89","datavalue":{"value":{"entity-type":"item","numeric-id":311578,"id":"Q311578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715067$19960EF5-65CE-47C2-A7B9-840AE92DA6EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"96808ec2b5088e80297b25b2cbc13c394f973749","datavalue":{"value":{"entity-type":"item","numeric-id":311558,"id":"Q311558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715067$856C9B78-4538-4180-8ECB-E51B292F15D8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715067$71A5BF01-EB6A-4B22-B16C-17E2E7BA33E0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3f4145805478faad59761c3ff4a8cc3fff513172","datavalue":{"value":{"time":"+2019-02-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1715067$B9E2B9EE-DB89-42EC-B1D7-CE1DEFFA61D5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2819070a9b50ef16fdbffb5519677d44bbc41e01","datavalue":{"value":"https://arxiv.org/abs/1602.02589","type":"string"},"datatype":"url"},"type":"statement","id":"Q1715067$577259EE-2C04-44F9-83CC-994C7B18E77A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"345444e7527e702ad45fa4e6811b6453a75aec09","datavalue":{"value":"A $k$-coloring of a graph $G$ is an assignment to each vertex a color among $k$ different colors such that adjacent vertices get distinct colors. A graph $G$ is $k$-colorable if it has a $k$-coloring and its chromatic number is the least integer $t$ such that $G$ is $t$-colorable. A graph $G$ is $k$-critical if $G$ is not $(k-1)$-colorable and every proper subgraph of $G$ is $(k-1)$-colorable. For a graph $G$ with chromatic number $k$, every minimal subgraph with the same chromatic number $k$ must be $k$-critical. One natural question is that how few edges can an $n$-vertex $k$-critical graph $G$ have? In the present paper, the authors improve the best known lower bound on the number of edges in a $k$-list-critical graph. Their proof uses the discharging method, thereby making it simpler and more modular than previous work in this area.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715067$0C2CE3D0-7AD0-4DA7-B848-C16F697F8846","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"99fea3d876487c7181e0dff689e3c55a44323330","datavalue":{"value":{"entity-type":"item","numeric-id":592071,"id":"Q592071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715067$A45C6507-54D3-4334-93C2-613D6A0AD446","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715067$B12B11F9-AD04-4FFA-9965-A829CED45608","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9704779f550a58aa15a485e127fe20128292c66b","datavalue":{"value":"7011203","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715067$C5FBC727-D606-41E1-BAFF-146A1325DAE3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4e2a5d2d3ab2fcfe4dc5f7c0e155ee6c2f2929","datavalue":{"value":"$k$-colorable graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715067$20DB81F4-588F-423E-AC14-8BAB6B23DA2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3627b2fe432e74475852bad41b91dc75ab7cd870","datavalue":{"value":"$k$-critical graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715067$45FC59DF-E3E7-43DB-9E7A-CC4A22632020","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715067$0378086D-71D5-45AC-8AC9-581C268136C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78911e788d295f0f0c33ce87333fb0187723547a","datavalue":{"value":"list critical graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715067$E69A550B-787E-4C96-88CA-72B9748FCA37","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":"Q1715067$810B8797-36D8-44C7-BD3B-A6A3E41F677D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a3af24b40ecf62a7929cfe4e0a2a3fec2af63c5a","datavalue":{"value":"W2257967166","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715067$3C0D4AFF-27F1-48AF-8E61-F0760309726E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8fcbe63c18d9f7ba35a33c221019338c2f819c1c","datavalue":{"value":"10.1007/S00493-016-3584-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715067$E58341EE-A340-478E-94B8-A94CC5429FAD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f6c1b3fc0c9a52f6baeabd1ffc0c0c61bdb105b","datavalue":{"value":{"entity-type":"item","numeric-id":1405127,"id":"Q1405127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"653bdccae0a979b000abe26a3e65e5e3fdb64d4f","datavalue":{"value":{"amount":"+0.8366994261741638","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":"Q1715067$60FD27D2-F8EF-4211-85B7-19857CC96C96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"038e4deeae01c82afc5385709ffca9481242b06c","datavalue":{"value":{"entity-type":"item","numeric-id":462926,"id":"Q462926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5efb2e01603aa2347a4a8e11f36cab21af1a8f52","datavalue":{"value":{"amount":"+0.8353098630905151","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":"Q1715067$B50E340B-8A62-4A42-BFE7-D3FE413BD566","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cad9b2d7529748ed7247854b0a371b5f79a61cc","datavalue":{"value":{"entity-type":"item","numeric-id":2284728,"id":"Q2284728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe258f3db756fed5d491291022b1d7de2b5fdadd","datavalue":{"value":{"amount":"+0.8146559000015259","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":"Q1715067$81059FC4-DDD0-4566-954B-5AD12B464516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b0a53157406e226c2ad6c5c2204e36ca332745d","datavalue":{"value":{"entity-type":"item","numeric-id":4250145,"id":"Q4250145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d34b2513c1017cfa3157379fec4921ae76eee5e","datavalue":{"value":{"amount":"+0.8131160140037537","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":"Q1715067$84614EB2-2F95-4F11-BF05-4F09F9195277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b288ccbf79987b16b48a7ae3d2fa2ebf1de28d0f","datavalue":{"value":{"entity-type":"item","numeric-id":1584424,"id":"Q1584424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85aa85009b684340efec5ba22f21f8180d72dc49","datavalue":{"value":{"amount":"+0.8114867806434631","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":"Q1715067$8C6FB53B-550C-4F48-8CFF-239BD0229070","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Edge lower bounds for list critical graphs, via discharging","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Edge_lower_bounds_for_list_critical_graphs,_via_discharging"}}}}}