{"entities":{"Q521386":{"pageid":523153,"ns":120,"title":"Item:Q521386","lastrevid":62494602,"modified":"2026-04-11T06:28:37Z","type":"item","id":"Q521386","labels":{"en":{"language":"en","value":"An inertial lower bound for the chromatic number of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6703750"}},"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":"Q521386$CEDBEF23-5746-4872-9B96-5E8E817A3213","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"df1f6b377490d1e5f6fd627a9245f14c68698a3c","datavalue":{"value":{"text":"An inertial lower bound for the chromatic number of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q521386$CE9B2DAA-D3DA-4339-A682-9EA690018291","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"68ddc710be4ba0798c7ef0407d6cdcaa62595575","datavalue":{"value":"1358.05104","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q521386$BEB1ED7D-249A-4C45-9F05-92EE6EE53AF9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"295da0f91db885693be42323023047b48ace2ba4","datavalue":{"value":{"entity-type":"item","numeric-id":297909,"id":"Q297909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521386$9F924B1A-C1A8-4E2C-8916-7D27D197536C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f347f39bb24bb29b5ea6e994d0a2d541f7b7b14a","datavalue":{"value":{"entity-type":"item","numeric-id":871275,"id":"Q871275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521386$97F3CE63-A86E-42FD-872C-3F6ED4C73E4E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521386$4DAD62D4-7146-4BAA-B1D2-8D7F0EACF2E1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c018a10501084d0b87c78551bc55b3f7e17eb53","datavalue":{"value":{"time":"+2017-04-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q521386$B14139C1-97B3-42AC-8BFA-4B79EF435E22","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e676feed2671cc78a63dfff3001e31421b6b0982","datavalue":{"value":"https://arxiv.org/abs/1605.01978","type":"string"},"datatype":"url"},"type":"statement","id":"Q521386$9CA684B7-A1B4-4B51-BD3A-368B78BC34D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"59c1d268660da79e393229899da81475b3045adb","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p58","type":"string"},"datatype":"url"},"type":"statement","id":"Q521386$6AD83F4D-DC5E-46E3-BF02-927631C481F5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"72c6d6ed3f5d532cd20adc245dc052ea35b670b9","datavalue":{"value":"Summary: Let \\(\\chi(G\\)) and \\(\\chi_f(G)\\) denote the chromatic and fractional chromatic numbers of a graph \\(G\\), and let \\((n^+, n^0, n^-)\\) denote the inertia of \\(G\\). We prove that:  \\[  1 + \\max\\bigg(\\frac{n^+}{n^-},\\frac{n^-}{n^+}\\bigg) \\leq \\chi(G)  \\]  and conjecture that  \\[  1 + \\max\\bigg(\\frac{n^+}{n^-},\\frac{n^-}{n^+}\\bigg) \\leq \\chi_f(G).  \\]  We investigate extremal graphs for these bounds and demonstrate that this inertial bound is not a lower bound for the vector chromatic number. We conclude with a discussion of asymmetry between \\(n^+\\) and \\(n^-\\), including some Nordhaus-Gaddum bounds for inertia.","type":"string"},"datatype":"string"},"type":"statement","id":"Q521386$E48FEB22-95AD-4C62-884E-CFE6C5359746","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q521386$5F2ED2E5-24FB-4B98-94A8-4A9E8EC2FF95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q521386$08B00FB7-0AC2-4FB1-A5CE-CBCD42A27FE8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bf2175aa6f9d8c61fa139b86effa257c74ad2fcd","datavalue":{"value":"6703750","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q521386$93EA33C5-91E7-450D-A9F8-06013D6F9CBD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05be6754d4964f25be10115147d1ff0acee655b9","datavalue":{"value":"spectral graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q521386$83D7BA98-E7BA-4314-BF0A-987CA3640BAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q521386$52041066-B4A7-48FC-8CDE-AF24253CD9DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"637872e1bd0dd812655871ae455bcab7bf55fd2b","datavalue":{"value":"fractional chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q521386$B3C9B6D3-4FEF-47E2-9856-0E7050F82CE2","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":"Q521386$BCD3E957-C1E9-4AD9-B78E-1D88A1FA75C9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"afdd7eae25d398685332cdfd8e8172a495611b1a","datavalue":{"value":{"entity-type":"item","numeric-id":745214,"id":"Q745214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521386$BE3F36CC-8B97-47CC-95FB-93BE2EDB2C28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a8064a6d20c8f7a15265aabd58052cec835dfec","datavalue":{"value":{"entity-type":"item","numeric-id":1941378,"id":"Q1941378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521386$82D1DA3C-BA9C-490A-95B1-92F13461D668","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eea809636efacf872d399265fc2055c53f30afb3","datavalue":{"value":{"entity-type":"item","numeric-id":2496209,"id":"Q2496209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521386$9F11BD45-1D48-4505-BB60-F0E3B6FBB9EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82b1f5bb9b2b34829bd2ea0d9e032b7aee52b216","datavalue":{"value":{"entity-type":"item","numeric-id":649184,"id":"Q649184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521386$C023A7DB-8D7B-4F64-969B-4ED08A8D9CB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b27cdb9da2abf4554881ffe2541524ba93fa94f","datavalue":{"value":{"entity-type":"item","numeric-id":1025479,"id":"Q1025479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521386$9E2B9378-155C-499D-819C-C77F7A3D8DD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc5bdf8847138dd2f239a0f343d48f700952111d","datavalue":{"value":{"entity-type":"item","numeric-id":891325,"id":"Q891325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521386$BBE40804-CB9E-4358-94D2-46CF7C3B5346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b102e362726431def7fabdee38d8139d9d53d46d","datavalue":{"value":{"entity-type":"item","numeric-id":3453101,"id":"Q3453101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521386$56BF3336-C2FB-4753-A379-D5260CB9A7C4","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":"Q521386$029A4D88-24B4-4414-AB32-A4E146C072F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d82615d2a514e1fa7a4b0fedce70eccee9925e4a","datavalue":{"value":{"entity-type":"item","numeric-id":2451220,"id":"Q2451220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521386$731DA505-4419-4E3E-AC57-E1E3783E10ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fe8ffb5d320c7f4d10668e009705b78461117ae","datavalue":{"value":{"entity-type":"item","numeric-id":550640,"id":"Q550640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521386$FF3EEA03-0671-4F7F-BD92-A70E39F60CD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7787b963b2efe6a08377df8962c70798529a4f0a","datavalue":{"value":{"entity-type":"item","numeric-id":996333,"id":"Q996333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521386$135E26AC-5BD2-453A-BD33-FA7176626AFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0a5079a0432ff28548bc129e4f0aff9c8d3621a","datavalue":{"value":{"entity-type":"item","numeric-id":492762,"id":"Q492762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521386$1CB6A184-ED3B-4887-97A4-14756DAE3F04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39955230987edbd9b04725f49e22d86a615e40b4","datavalue":{"value":{"entity-type":"item","numeric-id":3231818,"id":"Q3231818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521386$FBAD9BAE-F9C1-4F38-AFAF-CB2F5ABBB2B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c2e2e4311c473580c20032b915fd931c9c5f868","datavalue":{"value":{"entity-type":"item","numeric-id":396873,"id":"Q396873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521386$C5D3B629-7F82-479C-8459-DB004F0F8DD0","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"5b704893e3659b1584d6e6d2f5455da6e890caef","datavalue":{"value":"bafkreif2owal2wgu6utqgqrboyqssb4wmdqmwlmq7rui7r7ci5vfsqiohi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q521386$6AD34B0B-6DE6-4E1F-967E-78A86E6DEF54","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"337230cc9cbf10078d71985a9fd2f02420738333","datavalue":{"value":{"entity-type":"item","numeric-id":396873,"id":"Q396873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3355d81c8610a2ebb6292879d4d624c9cfe442f4","datavalue":{"value":{"amount":"+0.7821049094200134","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":"Q521386$7DEFFD4E-1B18-4AEF-B697-5CF72EDE7D0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8de0c0fc10f49828ac1b5874a0b0f66945d4b17","datavalue":{"value":{"entity-type":"item","numeric-id":996333,"id":"Q996333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b2d6f0ef8fbe46499b9c5b93a6b376a9915c437","datavalue":{"value":{"amount":"+0.7782532572746277","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":"Q521386$9F7DF3E8-C7EA-400E-A5FE-E6B45C5321D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04a0d85c57ba2aa2c644c705d051598f41fc7cdb","datavalue":{"value":{"entity-type":"item","numeric-id":2020660,"id":"Q2020660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c3c55557312fedd827b820d76830b151ed852ed","datavalue":{"value":{"amount":"+0.767663300037384","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":"Q521386$C80B41B4-9F9D-49EE-929D-9A1A6539FF00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aca6d6b028e1948bca0d0f734b07c2f57c29bcaf","datavalue":{"value":{"entity-type":"item","numeric-id":1704091,"id":"Q1704091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89e57371fa07681f48f2fc702840412ba159bdfc","datavalue":{"value":{"amount":"+0.7651703357696533","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":"Q521386$74C0EAC9-D42E-4AC3-9E1E-2680A3402427","rank":"normal"},{"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":"75905432ce33b6a01b7c6aab75a9fac06fb24998","datavalue":{"value":{"amount":"+0.7621469497680664","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":"Q521386$B312CC3F-7113-449A-A10F-ADA21EAFEEB3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An inertial lower bound for the chromatic number of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_inertial_lower_bound_for_the_chromatic_number_of_a_graph"}}}}}