{"entities":{"Q491554":{"pageid":493321,"ns":120,"title":"Item:Q491554","lastrevid":62237199,"modified":"2026-04-11T04:42:17Z","type":"item","id":"Q491554","labels":{"en":{"language":"en","value":"Representing graphs via pattern avoiding words"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6475727"}},"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":"Q491554$D61F0CBC-24DC-40C4-8F6D-45E0B4B12275","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4a9be6256780bcbecfb195a0f812d69defc5fab8","datavalue":{"value":{"text":"Representing graphs via pattern avoiding words","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q491554$3E467472-5B8A-48D0-B621-4F7F38DC56F2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"320f58bc85128701366a6c31da91d96d5dc115a1","datavalue":{"value":"1319.05092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q491554$0C1E2B10-A884-43FE-9027-0F160A236CCB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"93d5b529cb72dbee5219c8278759bd209575efcd","datavalue":{"value":{"entity-type":"item","numeric-id":284735,"id":"Q284735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$638E61A7-4696-44D5-B4CF-84F267C54E30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"db2bbebb5f462d46d3aa45617e767605322b5475","datavalue":{"value":{"entity-type":"item","numeric-id":394207,"id":"Q394207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$05F08559-87B0-496F-B043-3410ACA007BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d68f8af43e3f9129c14f4425cce76d6c8c7fb32c","datavalue":{"value":{"entity-type":"item","numeric-id":334415,"id":"Q334415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$F97B9722-1BE5-4A2B-9A22-7A44EEBEA3F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5dc30c87ee90e636f091c198a5b55721665c69f9","datavalue":{"value":{"entity-type":"item","numeric-id":698606,"id":"Q698606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$D72252C4-C5CF-4CCF-BECD-96B07D268E55","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":"Q491554$BC8BBB04-5DB0-4F69-9D10-09D09489C11F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ddf6ecb9e5ed20bb1adfdb1d89c4230618bbee22","datavalue":{"value":{"time":"+2015-08-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q491554$97A3F9A0-9484-4794-A69E-2F082938BF9F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4313b6f0a3077fcaf272382df39fd0666314e1b1","datavalue":{"value":"https://arxiv.org/abs/1412.4994","type":"string"},"datatype":"url"},"type":"statement","id":"Q491554$9235A30F-8A8F-4DCB-8C62-090E5AA24610","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"c5028a2276f4f83aba47ba27d910e9d1e65d4b61","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p53","type":"string"},"datatype":"url"},"type":"statement","id":"Q491554$AF9C2CC1-C82D-4065-BE94-9CBDF28C8086","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0e429e5d88221340ee2201a84df2ddebb274297a","datavalue":{"value":"Summary: The notion of a word-representable graph has been studied in a series of papers in the literature. A graph \\(G=(V,E)\\) is word-representable if there exists a word \\(w\\) over the alphabet \\(V\\) such that letters \\(x\\) and \\(y\\) alternate in \\(w\\) if and only if \\(xy\\) is an edge in \\(E\\). If \\(V =\\{1,\\dots, n\\}\\), this is equivalent to saying that \\(G\\) is word-representable if for all \\(x,y \\in \\{1,\\dots, n\\}\\), \\(xy \\in E\\) if and only if the subword \\(w_{\\{x,y\\}}\\) of \\(w\\) consisting of all occurrences of \\(x\\) or \\(y\\) in \\(w\\) has no consecutive occurrence of the pattern 11.     In this paper, we introduce the study of \\(u\\)-representable graphs for any word \\(u \\in \\{1,2\\}^\\ast\\). A graph \\(G\\) is \\(u\\)-representable if and only if there is a vertex-labeled version of \\(G\\), \\(G=(\\{1,\\dots, n\\}, E)\\), and a word \\(w \\in \\{1,\\dots, n\\}^\\ast\\) such that for all \\(x,y \\in \\{1,\\dots, n\\}\\), \\(xy \\in E\\) if and only if \\(w_{\\{x,y\\}}\\) has no consecutive occurrence of the pattern \\(u\\). Thus, word-representable graphs are just \\(11\\)-representable graphs. We show that for any \\(k \\geq 3\\), every finite graph \\(G\\) is \\(1^k\\)-representable. This contrasts with the fact that not all graphs are 11-representable graphs.  The main focus of the paper is the study of 12-representable graphs. In particular, we classify the 12-representable trees. We show that any 12-representable graph is a comparability graph and the class of 12-representable graphs include the classes of co-interval graphs and permutation graphs. We also state a number of facts on 12-representation of induced subgraphs of a grid graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q491554$D568E3D4-E999-4C05-A141-3C8D0610341B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q491554$882BB6A2-599B-44F0-8BB2-F0C33F3AA98D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f058b56fcd80b43a5e2499a4c023530bd01db4e5","datavalue":{"value":"6475727","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q491554$2D5951C7-B6BC-4D44-B647-4A39718D74FC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec18bed2f509a7836f9a4c7e0cd62a6499a24756","datavalue":{"value":"word-representable graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q491554$9DA69C5C-81B1-4D0C-AB53-0F5EBD6798CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d589d1418bb454d0d57abd8c2020b4fc06552aa","datavalue":{"value":"pattern avoidance","type":"string"},"datatype":"string"},"type":"statement","id":"Q491554$CF6AF33A-209A-4932-B335-40BD38472516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"329e1c13daa8aa98a20a699b2b1edca88d38cf5a","datavalue":{"value":"comparability graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q491554$C5E8CCE2-03E3-4D41-BA6D-CF544704B3FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"031b47863a1e829bed8048060a811d1dc6f8579a","datavalue":{"value":"co-interval graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q491554$0C254A9E-FA64-443B-9C9E-46F50A0E5257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"972b47051b12a25f42ccd0a9702464009e0dcd44","datavalue":{"value":"permutation graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q491554$C0035CEE-C827-416E-BCB9-28337B617EE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3d009c78b4a6a98a7e969740d48b52bd7730b8d","datavalue":{"value":"grid graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q491554$032F71E1-7B45-485B-B75C-AE1376E81F20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff4ee59479639ecb7e8375f724854d79769b9be6","datavalue":{"value":"ladder graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q491554$11CE422D-5D24-459A-BA9C-8689BF1ED4CB","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":"Q491554$6EEEFE82-C24C-4D9D-AC5E-911EEF6232AD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1040e0d9051b4c4d815f1bdfe64236ec8c01017f","datavalue":{"value":{"entity-type":"item","numeric-id":894291,"id":"Q894291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$4D9625DC-85C7-4B3B-86C4-2D0CAF808924","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aaf7b8579329268d4b468ae805c3d282b2b05946","datavalue":{"value":{"entity-type":"item","numeric-id":5659598,"id":"Q5659598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$92EEC358-A7A5-452A-8504-42D16FC8656F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"922cd1770b5809cfa6b8b3134475e67151df26a2","datavalue":{"value":{"entity-type":"item","numeric-id":344843,"id":"Q344843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$E71F2A6F-1CCF-4FFC-8E27-2867E5723B9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c17b1143dff0bc685088f8d62dbc046a1f96e02e","datavalue":{"value":{"entity-type":"item","numeric-id":5732670,"id":"Q5732670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$43751E5E-C954-40CC-AD6E-635EE8199384","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"595edbfdd0d52ff2f8b68613f9c4527dd982c71c","datavalue":{"value":{"entity-type":"item","numeric-id":3584914,"id":"Q3584914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$DBEE2FBF-EC85-490B-8D4F-F668DDB6A3E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7f655e089d77ec6463c4129ec83bb9e42dbb8e9","datavalue":{"value":{"entity-type":"item","numeric-id":3104776,"id":"Q3104776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$B3A185BB-EBC5-4343-B617-6C34613C1EE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3797be036acdf0481cf7abd2cad30dfc42746bfe","datavalue":{"value":{"entity-type":"item","numeric-id":632372,"id":"Q632372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$1E831EF6-6DB7-4F9D-9D00-5E0BE63FF34D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d714e27262d080224784cc9fc21bc7b61f3ab8da","datavalue":{"value":{"entity-type":"item","numeric-id":5507086,"id":"Q5507086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$1271C727-7AD1-4026-9863-0DDABF6915CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38387dd0273b477ac8ccd202ac26477d7d5378ee","datavalue":{"value":{"entity-type":"item","numeric-id":897110,"id":"Q897110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$E07BDE43-E602-435F-9779-8110B4D781B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18ac5561064b100d296c03d31b9f4ed4ffe582ed","datavalue":{"value":{"entity-type":"item","numeric-id":5503439,"id":"Q5503439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$0360002C-D854-4853-85ED-9765F19D8F80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5eafc1b15f6ceb65b3cc1df78950c9b4a711658c","datavalue":{"value":{"entity-type":"item","numeric-id":5199997,"id":"Q5199997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$BAFBACC9-6001-4A99-84AC-730B8A9DE69D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fac41ff8b976220a9456dd36888ad291a43f1aa","datavalue":{"value":{"entity-type":"item","numeric-id":5350464,"id":"Q5350464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$413DE052-D880-4768-89B7-3A170A6C73C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28a8dac2e5b92828c9fc58afc2e01c2f0b9a28c4","datavalue":{"value":{"entity-type":"item","numeric-id":953264,"id":"Q953264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$9C9933FF-D05B-4684-A43D-A94733CD912C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f75dd47304db8c29d81e98b64f2b7cde56acf821","datavalue":{"value":{"entity-type":"item","numeric-id":4791727,"id":"Q4791727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491554$0274E11F-928A-4CA8-BB22-172784A86D0F","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"658fd8e80d15c397dbcc6f852065a997629d7c1e","datavalue":{"value":"bafkreig5oilhpstu5kgfh5gluovxm7sm3ufxhiqy7k5x6erlqlzsdibu6e","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q491554$F77DBA05-D9ED-4EDE-899F-9CA192855E09","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d3bf6370d24739eb17c6c1d0f6f5e047ba6c6f7","datavalue":{"value":{"entity-type":"item","numeric-id":4595641,"id":"Q4595641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88dbc805be317cad61bcdbe94b6c94a8357f54ed","datavalue":{"value":{"amount":"+0.9057785868644714","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":"Q491554$00F597AB-F50A-4E62-9E68-98A300118B2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84d3e05ce9aaae408d1b241864741565d9025fda","datavalue":{"value":{"entity-type":"item","numeric-id":1717191,"id":"Q1717191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab92127d06930a1f0f776660a8dd0bb04bcb83fa","datavalue":{"value":{"amount":"+0.8802122473716736","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":"Q491554$0951DB51-1A73-4A6E-951B-5A864EF4934C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fa3db5ce68d5eece6e71916255b8c9941bed37d","datavalue":{"value":{"entity-type":"item","numeric-id":2416927,"id":"Q2416927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1f53e3dcfebf57c4e7692ad722dfc04a49fb8c3","datavalue":{"value":{"amount":"+0.8633683919906616","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":"Q491554$4A63B8AE-2CF0-4426-8918-6AD567279B20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"826d9f8d27f8b46598a518a828e964fb7a8bc9bb","datavalue":{"value":{"entity-type":"item","numeric-id":5503439,"id":"Q5503439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c52e1fd172f29f21e1d769b89b078531fb293145","datavalue":{"value":{"amount":"+0.8520827889442444","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":"Q491554$4740D8D7-D709-4036-8BDE-F76FFB711B26","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Representing graphs via pattern avoiding words","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Representing_graphs_via_pattern_avoiding_words"}}}}}