{"entities":{"Q1850041":{"pageid":1860783,"ns":120,"title":"Item:Q1850041","lastrevid":69353868,"modified":"2026-04-13T06:26:31Z","type":"item","id":"Q1850041","labels":{"en":{"language":"en","value":"Dense critical and vertex-critical graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1839022"}},"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":"Q1850041$B3D0391D-50FB-4480-AE4E-C964B50D0C81","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"49782ba2ccac1f1a7d57a3c019360e79480627a1","datavalue":{"value":{"text":"Dense critical and vertex-critical graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1850041$CC045575-7709-429C-B50F-E3E9A99FAE17","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"58ce8ceeea0b2fd7b3fa411d6592fe5db83a2a6c","datavalue":{"value":"1007.05048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850041$1174DBA9-D63B-42E0-BEF8-AE2915A0C964","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"69b42ac165a2ddbd90cfe413d7d8c168e13093e7","datavalue":{"value":"10.1016/S0012-365X(02)00262-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850041$AC686B2E-6911-46B5-AF67-09E4C1A947AB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"93409a5d4c83acad8ef7f368187a086954481833","datavalue":{"value":{"entity-type":"item","numeric-id":518114,"id":"Q518114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850041$A334D8E4-239C-4098-B70A-B461F231F049","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":"Q1850041$640CE104-66D9-43EC-988E-3E5BEF9CFD05","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"82ac30fadc544187fd268bb88e1da4be75a5ee8c","datavalue":{"value":{"time":"+2002-12-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1850041$91723B09-25B8-4B7B-AD02-974B3B9E78F9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1ade5524160f4c17d9683fd97b32c0fb2e7cfb35","datavalue":{"value":"In this paper it is proved for \\(4\\leq k\\leq d\\) that there exists a constant \\(c_{k,d}\\) such that infinitely many \\(k\\)-chromatic critical graphs have minimum degree at least \\(d\\) and at least \\(c_{k,d}n^{2}\\) edges, where \\(n\\) is the order of the graph. Also a general bound \\(c_{k,d}\\geq cd^{-4}\\) for infinitely many values of \\(d\\) is derived. It is shown for \\(k\\geq 3\\) that there exists an infinite family of vertex-critical \\(k\\)-chromatic graphs containing at least \\(((k-3)n^{2}+(k+1)n)/(2(k-1))\\) edges, and for every \\(k\\geq 5\\) and every \\(m>0\\) that there exists a vertex-critical \\(k\\)-chromatic graph such that any subgraph remaining after deletion of a set of \\(m\\) edges incident with the same vertex is again \\(k\\)-chromatic. This extends a result of \\textit{J. I. Brown} [Discrete Math. 102, 99-102 (1992; Zbl 0768.05038)], who proved this statement for \\(k=5\\) and \\(m=1\\), thereby answering a problem by Dirac whether there exists a vertex-critical graph without critical edges. Dirac's original question for \\(k=4\\) remains unsolved, however.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850041$B3F08AA3-4287-4A97-83DE-C1F2A569C6B0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850041$DC273F79-8BCA-42A4-A1D0-FB4E19FED5D0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e8818968e2ca1ccb978a4583a8335838cec905df","datavalue":{"value":"1839022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850041$ADDABABB-95FB-4CD3-B4CB-BE4475883151","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850041$F859C4EE-1875-43FB-88C6-EBB78A026D1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"12596ffaaace3d67bdcc752628778f2bb9159ed1","datavalue":{"value":"vertex \\(k\\)-chromatic critical graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850041$7467536E-4C6C-471C-87A4-CB5CF83657D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850041$1A8016C9-7620-4F90-AC4E-C389C5A41BD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52f104390803a7569ae3f576b172d639d0061261","datavalue":{"value":"edge density","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850041$B4E4C560-9DD9-44FF-9C34-9330C1B3DAFB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850041$2079A8A5-4180-4AAA-8C5A-57268B36D220","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":"Q1850041$A814C91B-3296-4844-BF27-0746F029AD5F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a8b69e0186895709f9918b5b3e01f47eb6b6a07","datavalue":{"value":{"entity-type":"item","numeric-id":890907,"id":"Q890907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36d7edd4ae6c4c467a812019bc50fa9642684e12","datavalue":{"value":{"amount":"+0.887135922908783","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":"Q1850041$396692A7-E144-4ECA-B19C-0262ED11C9DE","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":"7f9ad98b2692920e820a42f6dd26d2480f8ae448","datavalue":{"value":{"amount":"+0.8714491128921509","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":"Q1850041$CBD64D1F-6E0C-4BFC-92A8-F0AB5026B5C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab9d023af290eb4a72aab9e5bd5230b143ebad86","datavalue":{"value":{"entity-type":"item","numeric-id":1366769,"id":"Q1366769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5e108fc572452e1ec96099f91fc4b4a6f3fed26","datavalue":{"value":{"amount":"+0.8547285199165344","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":"Q1850041$D5FAC2E5-7844-428B-84B2-4E6A8F117732","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb4e1d7e782143dd581ac023f78152babf040b1f","datavalue":{"value":{"entity-type":"item","numeric-id":1850068,"id":"Q1850068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53797a7c51b9fcc28b325c5ea28277eb2da969c9","datavalue":{"value":{"amount":"+0.8502405285835266","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":"Q1850041$D6971D41-6E69-4902-9C6D-52EFA69F65EF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Dense critical and vertex-critical graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Dense_critical_and_vertex-critical_graphs"}}}}}