Universality of \(A\)-mote graphs
type: Item
instance of: scholarly article
title: Universality of \(A\)-mote graphs
zbMATH Open document ID: 0799.05063
author: Roland Häggkvist
author: Pavol Hell
published in: European Journal of Combinatorics
publication date: 1993-05-16T00:00:00Z
review text: 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\)).
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 167692
zbMATH Keywords: finite loopless graphs
zbMATH Keywords: digraphs
zbMATH Keywords: homomorphism
zbMATH Keywords: homomorphic image
zbMATH Keywords: universal graph
zbMATH Keywords: \(b\)-bounded graphs
MaRDI profile type: Publication
full work available at URL: eujc.1993.1004
OpenAlex ID: W2003614121
DOI: 10.1006/EUJC.1993.1004
description: scientific article; zbMATH DE number 167692