{"entities":{"Q6177425":{"pageid":13312313,"ns":120,"title":"Item:Q6177425","lastrevid":55552654,"modified":"2026-02-17T18:42:33Z","type":"item","id":"Q6177425","labels":{"en":{"language":"en","value":"Coloring hammer-free graphs with \\(\\Delta - 1\\) colors"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7790208"}},"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":"Q6177425$EF965CEF-E3E8-43FC-B773-43FC6666604A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a445bf2b08ed2f1c4d7135ad95bb68cfa92a4c2b","datavalue":{"value":{"text":"Coloring hammer-free graphs with \\(\\Delta - 1\\) colors","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6177425$62CD4C46-D3A4-44E1-87DE-C5EF760C6FE0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3c1487aaed565a8f5171c9336eb47492d565565f","datavalue":{"value":{"entity-type":"item","numeric-id":254339,"id":"Q254339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6177425$067E5722-F741-4047-9EF4-343643C81563","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"076e4063b00b2fa65d753cf6618865b5ad2b3f93","datavalue":{"value":{"entity-type":"item","numeric-id":2109107,"id":"Q2109107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6177425$59703344-F6E6-437F-B9AE-111D06B1E0B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a52b84a5c0c5814f62a650fc17ec782450850926","datavalue":{"value":{"entity-type":"item","numeric-id":6154379,"id":"Q6154379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6177425$DC99AED4-9A83-4D4D-8AFA-0A6845F41A2A","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":"Q6177425$0AD32DC4-3D10-4EA0-99F8-B74A037E80D3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f3706e6c6666e19fa7ecd04e85d72fb77080ad2e","datavalue":{"value":{"time":"+2024-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6177425$CF7172AD-0477-4C3C-9513-DF9C36EE5B94","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"77e3043ffdac34a63da6abc63b6a0685c4acf4d7","datavalue":{"value":"This note focuses on the Borodin-Kostochka conjecture (BKC), which states that the chromatic number $\\chi(G)$ of a connected graph $G$ with $\\Delta(G)\\geq 9$ is less than or equal to the maximum of $\\Delta(G)-1$ and the clique number $\\omega(G)$. This conjecture proposes a bound on the chromatic number based on the graph's maximum degree and the clique number.  This note contributes to the field by proving BKC for a specific class of graphs, termed ``hammer-free'' graphs, where a hammer is defined as a graph formed by identifying one vertex of a triangle and one endpoint of an induced path with three vertices. The significance of focusing on hammer-free graphs lies in narrowing down the conditions under which the conjecture holds, thus making a step towards a general proof.  This work is crucial as it advances our comprehension of graph coloring, a fundamental concept in discrete mathematics and theoretical computer science. The insights gained from this study could lead to more efficient algorithms for graph coloring problems and a more profound understanding of graph properties and their impact on graph coloring.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6177425$F4C3B85A-41AD-4025-9E05-75A69005C110","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1e1f410656486c4808aa81d9aba4daecf2ae80c6","datavalue":{"value":{"entity-type":"item","numeric-id":993697,"id":"Q993697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6177425$4F1FBFFE-EF11-4C48-A5A1-97667208804A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6177425$E0EEA9C7-DCBC-4723-921D-CB3E693372F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6177425$C4BFEA2F-AA76-4A98-8B23-A8604F2BE8B1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b28252c09262c40d0c7ea430dceb066a6f8dd2c0","datavalue":{"value":"7790208","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6177425$AE157022-2EB3-45CB-B64B-681DDDEF502C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34df930ff718d85fe66422e0c6cb1be579219616","datavalue":{"value":"Borodin-Kostochka conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q6177425$24CF54CE-089E-4EF5-B43F-AA0D60883718","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q6177425$0F503CAF-A4F4-4511-9A1F-8852E4530FBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f4bc5ef64b80473f2dd853aa845c54c1eb0ce36","datavalue":{"value":"induced subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6177425$80F91531-18F2-4607-A7B7-1D4EB2214178","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":"Q6177425$DEA7D094-7708-4AC3-A80C-C9E0EFD6E343","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"67e393b8e79d12842759947d7f2b9beeaeff0924","datavalue":{"value":{"entity-type":"item","numeric-id":1229732,"id":"Q1229732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6177425$C545CF8F-BAC1-430C-94FD-341C9E9D9EDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a92ab907df072bb20a1057061523b1fdda43679","datavalue":{"value":{"entity-type":"item","numeric-id":5782525,"id":"Q5782525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6177425$9B346E1C-A1D9-4A54-829B-254EB5EFEEC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10a3060520d5d8f40ec3ce580e75dc97a428ae4a","datavalue":{"value":{"entity-type":"item","numeric-id":6046645,"id":"Q6046645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6177425$38366126-1AE1-4986-A65C-9A0A86D9D541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e80b2a7e692f8a41852839b5b71936cf8bb41f","datavalue":{"value":{"entity-type":"item","numeric-id":2649505,"id":"Q2649505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6177425$A68AFB79-F563-4BFA-B128-8B99EF73D2EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cda0a49ca0d53d97fe58d402ca2c4d240803d6b0","datavalue":{"value":{"entity-type":"item","numeric-id":3909076,"id":"Q3909076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6177425$2B9D082C-4EB5-4C2A-AFDE-3DF05B5CE1B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f0f05102d1acb49e70d449d1ebac6d1f45297ef","datavalue":{"value":{"entity-type":"item","numeric-id":1306303,"id":"Q1306303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6177425$8AC07BC9-6328-4754-A87F-200AB877E39C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"97ac51166ba236482ffaa2aa0577a05ca33b04fd","datavalue":{"value":"10.1016/J.DISC.2023.113823","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6177425$9A92327C-EA3D-4EA2-BDA8-D8677789DF64","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7e389de71354ced2291423c501a97fee53cec6a","datavalue":{"value":{"entity-type":"item","numeric-id":6046645,"id":"Q6046645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17423f7cdc6ec198285335c4e3b95559564d90e6","datavalue":{"value":{"amount":"+0.7299829721450806","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":"Q6177425$B9FF3822-EDA9-42C8-8664-C467DAAD8305","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7029cdc005029e2442c1075e6cc42cb8eaa70857","datavalue":{"value":{"entity-type":"item","numeric-id":6650716,"id":"Q6650716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55af043b2add4d71602c2e5b1a6890d80ee66751","datavalue":{"value":{"amount":"+0.717074990272522","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":"Q6177425$CBE6904D-7B44-45FB-8A00-0BA07C946A82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b8676f45b9a0df6f7dcffff38d889895abeddd1","datavalue":{"value":{"entity-type":"item","numeric-id":6143873,"id":"Q6143873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4226926d5214a68b0f4c3977d429e090eccf14e","datavalue":{"value":{"amount":"+0.7108562588691711","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":"Q6177425$BAD17699-7BA0-45A2-8297-076E7A3E333F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23157f6af253de2b42f23f6d553507970f7b918c","datavalue":{"value":{"entity-type":"item","numeric-id":472396,"id":"Q472396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3f869a16636ddfcee9a64c451f7d05449544f54","datavalue":{"value":{"amount":"+0.7068852186203003","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":"Q6177425$48C45E18-5AF5-458F-A1CF-1E68C53037A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"febf17efb42d45e161263cf63dd22196248bb9e9","datavalue":{"value":{"entity-type":"item","numeric-id":6154380,"id":"Q6154380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e742b554f6e97eb50ef410081383b11b0a31db9c","datavalue":{"value":{"amount":"+0.7047480344772339","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":"Q6177425$0B0F52B3-9213-48E4-AE34-889505141810","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6177425","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6177425"}}}}}