{"entities":{"Q2496209":{"pageid":2506952,"ns":120,"title":"Item:Q2496209","lastrevid":57944220,"modified":"2026-04-03T04:45:38Z","type":"item","id":"Q2496209","labels":{"en":{"language":"en","value":"Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5040286"}},"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":"Q2496209$991E7BF5-C8E8-4C61-A0E8-A0E6822B7BD3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6597d06768a37c8f9c6451239af198d634a51708","datavalue":{"value":{"text":"Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2496209$A9648784-7DAB-4796-BD71-987C647AECED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8c6db71d11ec78307911eea59ac5ca3fda6908ea","datavalue":{"value":"1094.05036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2496209$F53984EF-0F9C-4F64-842A-FF0AE49B337A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f7091779cae69de5d4973824140919032e2ef67c","datavalue":{"value":{"entity-type":"item","numeric-id":879158,"id":"Q879158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496209$3C5E526D-26A4-4CD5-9308-4095476D77B5","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":"Q2496209$DF131A59-4716-47E7-99F1-3F09E15A65C3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"695354130dab3a786d23413cb8a043a7f99b90ed","datavalue":{"value":{"time":"+2006-07-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2496209$E3B0FC5F-8591-4F84-9E01-A4EB6C66CFEE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"75f28417d37d727edf843a92d576a5d438623625","datavalue":{"value":"https://arxiv.org/abs/math/0407107","type":"string"},"datatype":"url"},"type":"statement","id":"Q2496209$71119F5E-AD6D-442C-8925-10DFF6EF43B0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7e71c9ee7b236e12de467726f2e0b6a710e23ed2","datavalue":{"value":"Let \\(G\\) be a graph on \\(n\\) vertices, \\(\\chi\\) its chromatic number, and \\(A\\) its adjacency matrix. Let \\(\\lambda_1\\) and \\(\\lambda_n\\) be the largest and least eigenvalue of \\(A\\). Hoffman's bound [\\textit{A.~J.~Hoffmann}, ``On eigenvalues and colorings of graphs'', in: Graph Theory Appl., Proc. Advanced Sem. Wisconsin, Madison 1969, 79--91 (1970; Zbl 0221.05061)] states that \\(\\chi\\geq1-\\lambda_1/\\lambda_n\\).   In this paper it is shown that the same bound, or slight modifications of it, hold for several graph parameters related to the chromatic number: the vector coloring number [see \\textit{D.~Karger, R.~Motwani} and \\textit{M.~Sudan}, J.~ACM 45, 246--265 (1998; Zbl 0904.68116)], the \\(\\psi\\)-covering number (introduced by \\textit{A.~Amit, N.~Linial} and \\textit{J.~Matou\u0161ek} [Random Struct. Algorithms 20, 1--22 (2002; Zbl 0993.05071)]) and the \\(\\lambda\\)-clustering number (introduced in the paper under review).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2496209$5467C1B8-FFC4-4BFF-A7F8-D850AA752305","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2496209$5DBFF53E-FA30-4D26-ABD2-77BA1588AEBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2496209$16F9E6F0-42C3-4479-B835-7DE0B5721E01","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"67bbfc14e1ed1417c1de86724842b32bdcdeca15","datavalue":{"value":"5040286","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2496209$0E96E4E5-99BD-4D28-AD1D-40965FB4AFA4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2496209$9FED9D3F-8538-41FD-AF94-9A20387A1D20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36063f073eab1c45ff9e533af48162560362f880","datavalue":{"value":"vector coloring number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2496209$49420455-D930-41E1-93E5-00179FB3C14A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f96689ed6adbf93a1029059033645daf8ebdc0c9","datavalue":{"value":"\\(\\psi\\)-covering number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2496209$064AF37B-373D-4531-BDC8-3E88A14BEAA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d858dcf99450c886e4ad9051c63ba2413c82b534","datavalue":{"value":"\\(\\lambda\\)-clustering number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2496209$70B8F8E9-7B0A-4B4D-BAD0-3C3471D076B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"691bf65803ce46c891cca7bca61a81e9d88f042e","datavalue":{"value":"Hoffman's bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q2496209$E698FDA8-2834-46D4-BFB8-A64807A3206B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4c76e7e527ac5801c2f60b80c8c7bd5b1110bb9","datavalue":{"value":"positive semidefinite matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q2496209$E621CA26-FBFF-424C-8D4B-D3B77DE984E1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"02baa8c7a177bdddffdd29a44a9d552f63adf459","datavalue":{"value":{"entity-type":"item","numeric-id":582576,"id":"Q582576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496209$9B40465B-A26E-4808-A747-85FE01B243BF","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":"Q2496209$3071A9D8-24AE-4650-B394-F8093D2EB2D7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"564ad98eece0c6934369fb04f836ab1273c79b63","datavalue":{"value":"W2002478783","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2496209$1B4E745B-2792-49CD-9A89-A80482528993","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6881a40a0236cb2967f4db3bdfb9c63417d3ca9","datavalue":{"value":{"entity-type":"item","numeric-id":4534214,"id":"Q4534214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496209$A2D56D6D-2FC8-4532-9A60-163FB8C7D20E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae74673845da4e2ec58ea2c5bacae070cf1d5538","datavalue":{"value":{"entity-type":"item","numeric-id":5625207,"id":"Q5625207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496209$23A5E4EB-94B3-4906-AADD-FDAF928BD32F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de67154ac3679f10e545577bdf699216547737b3","datavalue":{"value":{"entity-type":"item","numeric-id":3841651,"id":"Q3841651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2496209$A4BC932A-3E5D-419C-BF6D-9871E90F77CD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"01d360e4f6408d34a07558e4c7ea0b854ba03343","datavalue":{"value":"10.1016/J.JCTB.2005.10.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2496209$1B893D87-3F6E-416C-8DC0-C5C3424BA181","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d23c4132c32ab33378d937c500485102d73076c","datavalue":{"value":{"entity-type":"item","numeric-id":2107750,"id":"Q2107750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9b0650d360709e4005bea2ae71f3adb4e8682df","datavalue":{"value":{"amount":"+0.8737603425979614","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":"Q2496209$4382C9E6-A87B-494B-ABD4-CFCE47782365","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c2fa4256ffe682364c435b242b7b83d248bd23b","datavalue":{"value":{"entity-type":"item","numeric-id":2215470,"id":"Q2215470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ffdbf4a00689275af76a2008945f7f6ea7e5d73","datavalue":{"value":{"amount":"+0.8630991578102112","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":"Q2496209$9FD1B1BA-7ADD-4F4B-972D-E0B17C94C1A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48d2710688a2062dfe56178993cf232877319a36","datavalue":{"value":{"entity-type":"item","numeric-id":2752204,"id":"Q2752204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ccd9243cb89716490446e2a5dfab3cbb39962b6c","datavalue":{"value":{"amount":"+0.8041765093803406","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":"Q2496209$DE53DC97-BB72-4E69-9123-5BA98A2BFE2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf84fd17ac2d6346dacc1cbfe6fe804b25ccfef7","datavalue":{"value":{"entity-type":"item","numeric-id":5006571,"id":"Q5006571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f3e0a052640e7b19755d6220c475805c1b227c7","datavalue":{"value":{"amount":"+0.8022279739379883","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":"Q2496209$91FEBE69-27C7-4F5C-A530-5F4D73E84EEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc93d24ff5dcc8864796208662eee182ae19defd","datavalue":{"value":{"entity-type":"item","numeric-id":891325,"id":"Q891325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1f3cb8b27d9e335fd80f3f5525c0148cb07ab2c","datavalue":{"value":{"amount":"+0.7919862270355225","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":"Q2496209$C57DF80D-7ABE-41D1-9AAC-7E7DBFCA5500","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2496209","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2496209"}}}}}