Universality of \(A\)-mote graphs (Q1209287): Difference between revisions

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\)).