{"entities":{"Q1422423":{"pageid":1433163,"ns":120,"title":"Item:Q1422423","lastrevid":68665641,"modified":"2026-04-13T01:17:47Z","type":"item","id":"Q1422423","labels":{"en":{"language":"en","value":"Coloring planar Toeplitz graphs and the stable set polytope."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2041905"}},"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":"Q1422423$CC7F1D0D-8221-4E61-BD5E-A0779DBBAFBE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b8f31e4d8dd8c6a32788ffcf4990f15c19186d00","datavalue":{"value":{"text":"Coloring planar Toeplitz graphs and the stable set polytope.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1422423$57C1DD33-98BB-4BB3-B791-7AA6C6D0F2E4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"85dc53f58cd374aa0538f36c3c4d775e1bfb5953","datavalue":{"value":"1039.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422423$45F4F616-4C78-4BA8-97C7-717D3F20C4C5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"28d631765e504438e3e38b9da799779910fba6a9","datavalue":{"value":"10.1016/S0012-365X(03)00315-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422423$B09DCCE4-F5DE-49EA-A5B1-35D1D419583C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"83c817a883a581cf1f40526d5315410b186d004b","datavalue":{"value":{"entity-type":"item","numeric-id":367043,"id":"Q367043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$AAF045C4-871C-4C8F-B0E5-CBF6EFAB20A4","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":"Q1422423$48FF2B56-6E7E-44E4-ADEA-2811C1130631","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1aee94454bbb3bb990b95de2d91d20cd9c9645ff","datavalue":{"value":{"time":"+2004-02-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1422423$4F1C2F7D-360D-4B5E-AF75-E6FF533D2AC1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7aab9173beac86a8aa8f8087753902f6834748e7","datavalue":{"value":"The first part of the paper studies the coloring problem of planar Toeplitz graphs, i.e., graphs with vertex set \\(\\mathbb{N}\\) where two vertices \\(x\\) and \\(y\\) are adjacent if and only if \\(| x-y| \\) is an element of a given set \\(I=\\{i_1,\\ldots,i_m,\\ldots\\}\\). If \\(I=\\{i_1,\\ldots,i_m\\}\\) is finite, the associated Toeplitz graph is shown to have exactly \\(\\gcd(i_1,\\ldots,i_m)\\) connected and isomorphic components. A Toeplitz graph is shown to be planar if and only if \\(I\\subseteq \\{1+i, 1+j, 1+i+j\\}\\) for some nonnegative integers \\(i\\) and \\(j\\). If the Toeplitz graph is planar with \\(I=\\{1+i,1+j,1+i+j\\}\\) and \\(i<j\\), denote the highest power of \\(3\\) dividing \\(i\\) by \\(3^r\\). Then it is shown that this Toeplitz graph is \\(3\\)-colorable if and only if \\(3^{r+1}\\) divides \\(j-i\\). Since all planar graphs are \\(4\\)-colorable and bipartite Toeplitz graphs have been characterized in [\\textit{R. Euler}, \\textit{H. Le Verge} and \\textit{T. Zamfirescu}, A characterization of infinite, bipartite Toeplitz graphs, in: Combinatorics and graph theory '95, Vol. 1, 119--130 (1995)] the chromatic number of any planar Toeplitz graph can easily be determined.  It turns out that if a planar Toeplitz graph is not \\(3\\)-colorable, then it contains a so-called \\((K_4 \\setminus e)\\)-cycle as a subgraph: Let \\((K_n\\setminus e)\\) be the complete graph on \\(n\\) vertices with one edge removed, and let \\(a\\) and \\(b\\) denote the vertices of degree \\(n-2\\), which are called the distinguished vertices. A collection \\((K^1,K^2,\\ldots, K^m)\\) of such \\((K_n\\setminus e)\\)'s is called a \\((K_n\\setminus e)\\)-cycle \\(C\\), if \\(K^i\\) and \\(K^{i+1}\\) have one of their distinguished vertices in common, i.e., \\(b_i=a_{i+1}\\) for \\(i=1,\\ldots, m-1\\), and possibly \\(n-3\\) of its neighbors; finally, \\(a_1\\) and \\(b_m\\) are connected by an edge. Such a \\((K_n\\setminus e)\\)-cycle \\(C\\) is easily seen to be \\(n\\)-critical with respect to coloring. Thus such a cycle may be seen as a common generalization of odd cycles and cliques.  The second part of the paper exhibits a facet defining inequality for the stable set polytope of a \\((K_n\\setminus E)\\)-cycle, i.e., the convex hull of the incidence vectors of its stable sets. Finally it is shown how Haj\u00f3s' construction can be used to further generalize \\((K_n\\setminus e)\\)-cycles thereby providing a very large class of \\(n\\)-critical graphs which are still facet-inducing for the associated stable set polytope.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422423$43AB5F09-4B58-414E-98C0-E50CBA4928C8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6dbc03ded8dc8f343dbb91f0750fa930e4a14011","datavalue":{"value":{"entity-type":"item","numeric-id":205838,"id":"Q205838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$F3D54379-B0B7-43FC-BD40-1B0C233200F9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422423$9C6648FD-5E60-4CA4-8670-226E9F119D49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422423$EF33BCB1-3CFE-4715-BCB8-66345D889168","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422423$864837E6-DA8F-43E9-ACF6-31F81B12CF79","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5606e9186ae23a3cdb709a4edffa6eec838bc569","datavalue":{"value":"2041905","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422423$05E7218D-40C2-40EC-A8C0-6D3BA8A17468","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422423$8D9E1F48-B273-4E56-8238-C5B91C7CD3D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"877406d33b02b093a509cd6008cc8a24cb2d0530","datavalue":{"value":"odd cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422423$BCA8BD9F-841B-47DF-8C28-7CFF07F7C050","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a153084f07a75cc56b26c617236589c3c4eb947","datavalue":{"value":"cliques","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422423$81A1341F-CDE1-41DA-875A-54B806FEF593","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":"Q1422423$F170BC9C-43A2-4916-A490-27AC79B8B41B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$7A3063E2-C540-48BA-94D7-19CFA26C78A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"887a3be5c0b6c2eec3077d94c8a6226fe330824c","datavalue":{"value":{"entity-type":"item","numeric-id":1179263,"id":"Q1179263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$D3C6D883-9C05-434B-909E-CEA7C18DBBE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d65efc553acb3341435472517f9846dc847b560","datavalue":{"value":{"entity-type":"item","numeric-id":4351316,"id":"Q4351316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$1FBC0FED-31FB-4632-8A14-2EECFC5AE367","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3ecc4ed854f4c2fb93ed2e8327283eb9cc15cf0","datavalue":{"value":{"entity-type":"item","numeric-id":1393418,"id":"Q1393418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$8D1E5FE2-810B-43E7-81D3-70CF79217033","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8d5159d81704a1ed87ffcbbabf89173e9c1908f","datavalue":{"value":{"entity-type":"item","numeric-id":1356742,"id":"Q1356742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$5E76C90A-9EA6-46D0-8541-22C9F1D75122","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5182d1fd961dad30e0b7624eb6d6ad84ca60d22","datavalue":{"value":{"entity-type":"item","numeric-id":800371,"id":"Q800371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$FC0320D7-85C6-4DBD-9900-47522C3D618A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b48cc324c1c275627051de4868db6788b100ebf1","datavalue":{"value":{"entity-type":"item","numeric-id":912118,"id":"Q912118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$5DEFC6F2-E24E-4434-B6B8-67BCFB04439B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bbfc6fab68d777a6e0b7cdbf31846ec0656420b","datavalue":{"value":{"entity-type":"item","numeric-id":5941501,"id":"Q5941501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$BAB9DDAA-D1DE-4416-A9BD-E153E709F4F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3e10f605dfffb86994767d640441b15df4f4935","datavalue":{"value":{"entity-type":"item","numeric-id":4414636,"id":"Q4414636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$D5CDE625-8379-48C6-ABB5-3D9835F03E56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$7C411073-389F-4028-B488-35DA8E9EC437","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccc9a34c170be980c30ba5dd1785f2eee64d5bc7","datavalue":{"value":{"entity-type":"item","numeric-id":1348117,"id":"Q1348117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$F89AFA31-FE93-403B-A330-C215D5AE8F1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"326be047f2c88d0da03ee9ff2d3e3fe6d79eb656","datavalue":{"value":{"entity-type":"item","numeric-id":1398261,"id":"Q1398261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$39CE219C-FD17-44AA-9664-813E3C0ECB44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35184f581a4fa42ee779b59d5e27eea0c204219f","datavalue":{"value":{"entity-type":"item","numeric-id":5931450,"id":"Q5931450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$AFCCFA4A-3AE7-40B4-B496-2988189A0BCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c11e32b8c76194ce124c8f46d0e23312d3c91983","datavalue":{"value":{"entity-type":"item","numeric-id":5936034,"id":"Q5936034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$159E7418-E258-457B-8AEE-67AD939C59B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4def438d8a28321802a44dbba53d7d9b373961a","datavalue":{"value":{"entity-type":"item","numeric-id":3923934,"id":"Q3923934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$D3F4928D-8832-45CB-9FA5-F3406AA7B12D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e138268b388c59cc350422a307264a1cbe02595","datavalue":{"value":{"entity-type":"item","numeric-id":5181532,"id":"Q5181532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$962C109C-86B5-4CC3-A5A2-CAEFFC519D21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae183667313cf787a047d7cc689faf768a7a9cf9","datavalue":{"value":{"entity-type":"item","numeric-id":1924138,"id":"Q1924138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$1E0CAC47-4DA7-483C-B059-418280E2C8EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed191515377c05d8727a8e720590b3fce042cb52","datavalue":{"value":{"entity-type":"item","numeric-id":1126180,"id":"Q1126180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$3E77B52C-9095-4609-92EF-DF5F23FDB360","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4fc2ab9efe36254466a838e21d1ded8363059db","datavalue":{"value":{"entity-type":"item","numeric-id":1377694,"id":"Q1377694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$0145A8C2-B60A-4848-BE38-931521727FBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55a3b5c93b3f2fef3326b3d318825580b3ce00dd","datavalue":{"value":{"entity-type":"item","numeric-id":4014311,"id":"Q4014311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422423$ADF9C5C2-396C-44C1-987B-1A56F9A87700","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee7604337efd0a31f5414cc93f2b7a0d661001b8","datavalue":{"value":{"entity-type":"item","numeric-id":2816082,"id":"Q2816082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51f19dd81ca907f4862443acd533c3f83f0457f5","datavalue":{"value":{"amount":"+0.853438138961792","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":"Q1422423$A89740B7-6200-48D0-B129-71F40F610244","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01f80da8c9338b7e69269a93d00bbbcf71279cd9","datavalue":{"value":{"entity-type":"item","numeric-id":4414636,"id":"Q4414636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d77fd954faa558e1c89a2cda0055fcbce9b62a2","datavalue":{"value":{"amount":"+0.8098641633987427","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":"Q1422423$FE8CBE82-DFB4-4FA1-B630-E2BAD3811404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a45eb2b273080456e129c6fdf5d6a7bb10f2d51e","datavalue":{"value":{"entity-type":"item","numeric-id":367045,"id":"Q367045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9a1fe4bc9bcd579cbdf8d03a83e51ea01cc645a","datavalue":{"value":{"amount":"+0.8046485185623169","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":"Q1422423$F466C368-96BA-4081-81D1-8ECD8DC9A21B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ef30bd05cd811c72364caf00c2a7599bd843aa6","datavalue":{"value":{"entity-type":"item","numeric-id":2883614,"id":"Q2883614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f592e3ce81ad64e7d8a3eff6a99bb29107428de0","datavalue":{"value":{"amount":"+0.799950897693634","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":"Q1422423$183CC4E2-417D-423C-B8ED-E705B961567C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe0ab4cfaa14bec03d6ed3a06bd5f50b7714e98a","datavalue":{"value":{"entity-type":"item","numeric-id":2448907,"id":"Q2448907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c95fd185d0234a72d6e85df2c523044214d0af5","datavalue":{"value":{"amount":"+0.7690477967262268","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":"Q1422423$14FA16AB-15AE-4214-A026-A5A776A1A90D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Coloring planar Toeplitz graphs and the stable set polytope.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Coloring_planar_Toeplitz_graphs_and_the_stable_set_polytope."}}}}}