{"entities":{"Q1209287":{"pageid":1220036,"ns":120,"title":"Item:Q1209287","lastrevid":66353004,"modified":"2026-04-12T09:31:31Z","type":"item","id":"Q1209287","labels":{"en":{"language":"en","value":"Universality of \\(A\\)-mote graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 167692"}},"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":"Q1209287$0CA7E17E-E832-47AC-B94C-01EBED7A1C95","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e8aa9fb4cf9e2001edcdb51171159fd0f9478cb3","datavalue":{"value":{"text":"Universality of \\(A\\)-mote graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1209287$D503BE08-E0A7-4490-9D5D-9F6F26880E69","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e49855c85a0507e4568f85b2896b720a4bb72774","datavalue":{"value":"0799.05063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209287$A5A9F519-51EE-4610-B2AC-728B23F72FFA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"db466ec026868779279f0c309eb8a29642f61f4d","datavalue":{"value":{"entity-type":"item","numeric-id":1165868,"id":"Q1165868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209287$E1CA5E1A-5AD7-4A54-86F0-EA9B67BCB894","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3b5375d01a59455d415f2afee9796bf93e2b3c4","datavalue":{"value":{"entity-type":"item","numeric-id":338573,"id":"Q338573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209287$653882C1-B72D-447E-8654-72028E89DDDF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209287$C1A9F29E-F30B-4ACE-839B-0EAF68F56A9E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1209287$5316604B-A86F-4C88-89D5-5E9B2E818EA7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ef59ec35518629afa2c1483da2d0ccb2d68583bb","datavalue":{"value":"We consider only finite loopless graphs and digraphs. For graphs \\(G\\) and \\(H\\), a homomorphism \\(G\\to H\\) is a mapping \\(f\\) of the vertex set of \\(G\\) to the vertex set of \\(H\\) such that if \\(gg'\\) is an edge of \\(G\\), then \\(f(g)f(g')\\) is an edge of \\(H\\). The graph formed by the vertices \\(f(g)\\) and the edges \\(f(g)f(g')\\), over all vertices \\(g\\) and edges \\(gg'\\) of \\(G\\), is called the homomorphic image of \\(G\\). If \\(A\\) is a fixed graph, we say that a graph \\(G\\) is \\(A\\)-mote if there is no homomorphism \\(A\\to G\\). A graph is \\(b\\)-bounded if the degrees of all vertices are bounded by the integer \\(b\\). If \\({\\mathfrak C}\\) is a class of graphs, we say that \\(U\\) is universal for \\({\\mathfrak C}\\) (or \\({\\mathfrak C}\\) admits a universal graph \\(U\\)) if each graph \\(G\\) in \\(\\mathfrak C\\) admits a homomorphism \\(G\\to U\\). (Note that \\(U\\) need not be a member of \\(\\mathfrak C\\).)   We denote by \\({\\mathfrak C}_ b\\) the class of all \\(b\\)-bounded graphs. Note that the class \\({\\mathfrak C}_ b\\) does admit a universal graph, namely \\(K_{b+1}\\). (This is another way of saying that any \\(b\\)-bounded graph admits a \\((b+1)\\)-coloring.) In this case the universal graph is itself a member of \\({\\mathfrak C}_ b\\). We shall show that if we restrict \\({\\mathfrak C}_ b\\) to its \\(A\\)-mote members (for a fixed connected graph \\(A\\)), we can find a universal graph which is also \\(A\\)-mote (although not necessarily a member of \\({\\mathfrak C}_ b\\)).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209287$F91CDD65-F5E2-4696-B3D5-1A924A3253A6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209287$CBA59859-C9A5-4B85-8377-03C9A1980322","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209287$0A514651-58E6-4790-BEDE-7CD198F253A3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"64cbe8726a513c40ea5f2fc958a50c7e278f418b","datavalue":{"value":"167692","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209287$C13CFE1C-2A5D-4F8B-AA5A-F34AE7BAEAAD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a3924032da06d7269a764ed740a649cc15e7d98","datavalue":{"value":"finite loopless graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209287$57BD1286-A476-406A-B8F5-B61693C0537A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ffa219ea2cff89df5162edb57bd2a31ea73e1a26","datavalue":{"value":"digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209287$1D18B92A-60D3-4171-841F-69AA621E160A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e636d6200f7544f4dd5a5bbed79f99982c70f6d","datavalue":{"value":"homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209287$053064B9-ADDE-4AAD-88A2-95DB324216A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c34ed688e11ead543686e2c22a4ea6a8fd199b0f","datavalue":{"value":"homomorphic image","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209287$F8BE99C7-A6E2-4092-9E5A-510779162D45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e739df749d6c867acd2763fc312bf2853a82972b","datavalue":{"value":"universal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209287$FA86BBAD-16B4-4233-97CD-6C8535F9FE11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7cf043fc34656d5c1c8094cbbe50c09a88234469","datavalue":{"value":"\\(b\\)-bounded graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209287$6C2E3CA0-A00E-42BD-9398-81D647C19B17","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":"Q1209287$F600EF04-5B01-463E-B569-ECC1324831E2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"303926d3bca84688817a98c51d8f93664ce38b1e","datavalue":{"value":"https://doi.org/10.1006/eujc.1993.1004","type":"string"},"datatype":"url"},"type":"statement","id":"Q1209287$B2BE0DA2-91BB-436D-8EBC-368691A5B911","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"861b3e837116ace71b9eae8bada75e4965cb014c","datavalue":{"value":"W2003614121","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209287$9AF7DE01-4AAD-4C1F-93A2-86D40507B644","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8c39eb544f17839eb62e7580c9f232616aba514f","datavalue":{"value":"10.1006/EUJC.1993.1004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209287$3394DE4E-0500-414C-99BD-ACA709C4130A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81f876d35d7fc9b756a364c2bbfa72eb8a5631fe","datavalue":{"value":{"entity-type":"item","numeric-id":3559387,"id":"Q3559387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b01af3b0fd6d7d000eebed43595bd41b0d33a726","datavalue":{"value":{"amount":"+0.817241907119751","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":"Q1209287$7016A44F-3737-4111-9853-A002562D22AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9234da1ef20f4962e536cbe0799401fc5ee70878","datavalue":{"value":{"entity-type":"item","numeric-id":1613451,"id":"Q1613451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8506d4cc97b59fabb413c1236a997af184d3936","datavalue":{"value":{"amount":"+0.8122146725654602","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":"Q1209287$5C9EC591-EE1F-4DF4-8914-D1422DB28A76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"308516a1d8bbc02eaeac07c85a5aa773b6a7fbbd","datavalue":{"value":{"entity-type":"item","numeric-id":1594236,"id":"Q1594236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8506d4cc97b59fabb413c1236a997af184d3936","datavalue":{"value":{"amount":"+0.8122146725654602","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":"Q1209287$FA9CD692-88EE-44DF-BAAB-CE939357D9B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3197027ae7875cfa7e8aefe78a795888de2c1281","datavalue":{"value":{"entity-type":"item","numeric-id":2407379,"id":"Q2407379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64f761db72590c2e3f8edee83fb4d58b5a1fa8ac","datavalue":{"value":{"amount":"+0.7990425229072571","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":"Q1209287$047F3016-0A99-4756-88BA-C4C807898C7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"877f3e5e20cdc0ddc3e00dd6ab3a48de2e0b3a73","datavalue":{"value":{"entity-type":"item","numeric-id":3496356,"id":"Q3496356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b3206aab036165217f62746061d61905b214365","datavalue":{"value":{"amount":"+0.7944704294204712","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":"Q1209287$40BE397B-E40A-4121-9F5F-B1BE9CF16B00","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Universality of \\(A\\)-mote graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Universality_of_%5C(A%5C)-mote_graphs"}}}}}