{"entities":{"Q1805321":{"pageid":1816063,"ns":120,"title":"Item:Q1805321","lastrevid":46368138,"modified":"2025-12-24T15:49:23Z","type":"item","id":"Q1805321","labels":{"en":{"language":"en","value":"A characterization of graphs with interval two-step graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 754006"}},"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":"Q1805321$6075F131-E88B-48A4-8C56-819A3B72CB15","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"94fae90e0f8e1fd1ea92ac7d166d1804c4ab707d","datavalue":{"value":{"text":"A characterization of graphs with interval two-step graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1805321$07E6ED5A-826C-4D7F-B343-57737919513F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e1575436622d781863ab7a7aae67af5c66417242","datavalue":{"value":"0821.05045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805321$D82CE760-8492-479B-A8AB-152F9F31B02C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3370d69f2db4e51e05f2071ce706025fa7fb5b37","datavalue":{"value":"10.1016/0024-3795(94)00173-B","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805321$94DC538C-C90A-4CDE-8EB0-CF7989D4AA86","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"926d9107e569bc78ce4c810073fe1ad53c4fdb22","datavalue":{"value":{"entity-type":"item","numeric-id":201979,"id":"Q201979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$979E435F-EB67-415B-8C62-39FA72E6CEE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fe46d2500dff092b332a0362382d3be4272a62c4","datavalue":{"value":{"entity-type":"item","numeric-id":201980,"id":"Q201980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$F392E926-F2DB-402E-9E66-D8E5085C28C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7e218545fb900251df4c99742c867e3742e703ee","datavalue":{"value":{"entity-type":"item","numeric-id":221676,"id":"Q221676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$E31206DB-4447-4E39-8090-38DD444ED973","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"961d5832b24c11b5bc4dc0c081c2ea7b2a93d800","datavalue":{"value":{"entity-type":"item","numeric-id":688261,"id":"Q688261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$8345C1A7-9B66-47AE-B948-CCDFCD292C29","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8de031de05325b44570d0c47c3ec8813873d565c","datavalue":{"value":{"entity-type":"item","numeric-id":92813,"id":"Q92813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$2FAF68A9-32B9-4F86-84B2-DB14E2DBC60D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"94c955202ea16fb64425904aba27ce80f6b7c4b7","datavalue":{"value":{"time":"+1995-09-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":"Q1805321$B6541B04-5389-4D01-9B01-2A268E98753C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9ea22d242270f8bb5291373aa4fb70488f6631da","datavalue":{"value":"The two-step graph \\(S_ 2(G)\\) of a graph \\(G= (V, E)\\) is the graph \\((V, E')\\), where \\(\\{x, y\\}\\in E'\\) iff \\(x\\) and \\(y\\) have a common neighbour. This concept is the undirected analog of competition graphs introduced in [\\textit{J. Cohen}, Food webs and niche spaces, Princeton U.P., Princeton, N.J. (1968)]. It is first shown that if the girth of \\(G\\) is 5 or \\(\\geq 7\\) then \\(S_ 2(G)\\) cannot be an interval graph.   Then the Gilmore-Hoffman characterization of interval graphs is introduced: a graph \\(G\\) is interval iff the family of maximal cliques has a consecutive ranking---that is, can be ordered \\(C_ 1,C_ 2,\\dots, C_ r\\) so that if \\(v\\in C_ i\\) and \\(v\\in C_ k\\), \\(i\\leq k\\), then \\(v\\in C_ j\\) for all \\(j\\) with \\(i\\leq j\\leq k\\). This characterization is used to find criteria for \\(S_ 2(G)\\) to be an interval graph for several classes of graphs: trees, graphs with neither triangles nor 6-cycles, graphs with no 6-cycles such that every edge is in a triangle, graphs with no 6- cycles, and graphs with no triangles such that no two 6-cycles share more than one edge.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805321$8E7F3CC7-DA42-4A49-B236-A0D879DB7C5A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805321$DCD8DFEE-D550-46C3-970A-6C382A9CDEB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805321$0C4CC045-7136-44DD-A35F-A8FC7E9D0489","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805321$05028A40-25C6-4384-A187-F777348DAC64","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"373498c31fbf64f76f33771070c5db5df6af0170","datavalue":{"value":"754006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805321$D1EF1991-9DBE-4FD0-8E14-347444F7179F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8333d2db80099089a89a1ee1cdf8697fc0ff39dd","datavalue":{"value":"two-step graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805321$DE34B5F7-CAC3-40C3-AD5C-B329460C1505","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a173748f93e4f70aa784451677e2ec88ea88e5","datavalue":{"value":"girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805321$71592B7D-236A-45BF-A84C-F18F6BD4C2B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a949c568749d2f4337e1772be827516d5211abc","datavalue":{"value":"interval graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805321$15498E56-8E7A-46B7-8218-EF67AADD2BAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"583a227ab7931dd2226572e00c948793be4b3f70","datavalue":{"value":"Gilmore-Hoffman characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805321$10461842-7F71-46A1-ABE5-138DBC421EE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f115a81543b37fe4640b1c297f0c9115ab3eeff5","datavalue":{"value":"maximal cliques","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805321$37D5C55E-B619-45B1-92B6-082F9EDEB7DC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"457b59512685cc959c2dfec1eb05d289a709afaf","datavalue":{"value":{"entity-type":"item","numeric-id":442385,"id":"Q442385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$B2FFDA10-13B7-4027-BF74-E677B7DEFE3F","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":"Q1805321$6A8D2E8F-CA97-443C-93D1-FE176B43B799","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a78dac468a12949526442acace60d0d12214fe76","datavalue":{"value":{"entity-type":"item","numeric-id":3803157,"id":"Q3803157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$C0260C7F-5652-4DC2-9A7D-DF0853FACA23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"495fd75465f8298ab14a64d707930037ed5210bd","datavalue":{"value":{"entity-type":"item","numeric-id":3472123,"id":"Q3472123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$70198D18-AB0A-4882-84B6-E20DA12850E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9914f8121a32baf6895c6797ec99c63c32102968","datavalue":{"value":{"entity-type":"item","numeric-id":1242450,"id":"Q1242450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$63918D5A-DB61-49CD-9F59-0FBA69EF97D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"806b21871fd6790913aba209dc13d66524ef9c90","datavalue":{"value":{"entity-type":"item","numeric-id":3820642,"id":"Q3820642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$83D24D26-B7BC-416A-96D0-87F33FC032C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c26c0e8ab719150b99b971f6f16d3f7da40826d","datavalue":{"value":{"entity-type":"item","numeric-id":3322121,"id":"Q3322121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$3AD7199D-5976-4966-9159-325960CDF756","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c74b7954c4e96ea2e676044196dc57d8b06146d","datavalue":{"value":{"entity-type":"item","numeric-id":2395457,"id":"Q2395457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$811E2546-5855-45D9-8ECC-F39EB551B44D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$4D716E8C-B377-46D2-8B6F-25E970DD7E18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6353279fddee5573dc10d14f93a30e2272dfce07","datavalue":{"value":{"entity-type":"item","numeric-id":1322181,"id":"Q1322181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$D9E7A3E5-DA84-4395-ADEC-635C27C045F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04ecaa1ba007fd5dcf65450700d0a743a68e209b","datavalue":{"value":{"entity-type":"item","numeric-id":1179189,"id":"Q1179189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$EA60C158-3E31-4867-8648-C58A92A540FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5f766e09eaaf6168691f27e599d9f658392ba8d","datavalue":{"value":{"entity-type":"item","numeric-id":3222864,"id":"Q3222864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$B823A96B-EB64-4322-AC63-625222D2E775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ee26d1e0597e3f299126081ddf68d90f4268005","datavalue":{"value":{"entity-type":"item","numeric-id":3977585,"id":"Q3977585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$D309331B-038F-42CB-BAF3-E5F34121A40E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0633bf1613411011940c11565f6fe8aa72366bb","datavalue":{"value":{"entity-type":"item","numeric-id":4863462,"id":"Q4863462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$B93CF198-EBE8-45EB-BBA1-D20DC7FFD54B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e14f31ff1a7a95cb71a1610149f3529db45c160","datavalue":{"value":{"entity-type":"item","numeric-id":4304373,"id":"Q4304373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$9108DBA4-8A6D-409C-B82D-C915DF809995","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"226c43f7660521158d9e5f55fc3089769452609a","datavalue":{"value":{"entity-type":"item","numeric-id":688262,"id":"Q688262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$EAF6E387-42CE-445A-982E-ADD0E98DD963","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03b52f0c547709e752093637aa1d167ce5cafac7","datavalue":{"value":{"entity-type":"item","numeric-id":688263,"id":"Q688263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$B35C2D75-AF7D-4606-A704-3E655D62E673","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42f104acc7eb5c29f12fb4eb680f4575e618e02b","datavalue":{"value":{"entity-type":"item","numeric-id":3689222,"id":"Q3689222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$9C70298D-8C9E-4F51-A2E6-2C8A97909A9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8592b19f12bd09556a4de81ad49778d747c4f77b","datavalue":{"value":{"entity-type":"item","numeric-id":4124209,"id":"Q4124209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$9BF83172-6AA4-46F1-B5AE-13C72B2807C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"014daf886ad1c7671f73161783fdcba93435137d","datavalue":{"value":{"entity-type":"item","numeric-id":4581633,"id":"Q4581633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805321$E118842C-0B57-49E6-97C8-53FB85345B9C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"713b1a1e17ec4f479abbca200ac855ab9d19361f","datavalue":{"value":{"entity-type":"item","numeric-id":688263,"id":"Q688263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2a3485d9395ef75ab4c7d30582379a040db0db8","datavalue":{"value":{"amount":"+0.8396251797676086","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":"Q1805321$9DE36C2A-CAF6-4B6E-9C22-005982659067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d014b251d8a4924181b6e152ef060703344be62","datavalue":{"value":{"entity-type":"item","numeric-id":4028469,"id":"Q4028469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"198faae56f8521222e1d31a473dfbbaae85cc05b","datavalue":{"value":{"amount":"+0.81169593334198","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":"Q1805321$F8A2BE58-1CF4-4FF6-8B9C-C78FBE6259EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22f517a382ab7fd803c7da2a1e9f8d1bf77cd32f","datavalue":{"value":{"entity-type":"item","numeric-id":688262,"id":"Q688262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef2bb2e59de9785f6912e71f309338319dd53c43","datavalue":{"value":{"amount":"+0.786555826663971","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":"Q1805321$B85BF1A6-1C59-4E33-8FF1-7CF11D1F76EC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1805321","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1805321"}}}}}