Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-08T02:08:05.664Z Has data issue: false hasContentIssue false

Homomorphism and Dimension

Published online by Cambridge University Press:  11 October 2005

PATRICE OSSONA de MENDEZ
Affiliation:
Centre d'Analyse et de Mathématiques Sociales, CNRS, UMR 8557, 54 Bd Raspail, 75006 Paris, France (e-mail: pom@ehess.fr, pr@ehess.fr)
PIERRE ROSENSTIEHL
Affiliation:
Centre d'Analyse et de Mathématiques Sociales, CNRS, UMR 8557, 54 Bd Raspail, 75006 Paris, France (e-mail: pom@ehess.fr, pr@ehess.fr)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The dimension of a graph, that is, the dimension of its incidence poset, has become a major bridge between posets and graphs. Although allowing a nice characterization of planarity, this dimension behaves badly with respect to homomorphisms.

We introduce the universal dimension of a graph G as the maximum dimension of a graph having a homomorphism to G. The universal dimension, which is clearly homomorphism monotone, is related to the existence of some balanced bicolouration of the vertices with respect to some realizer.

Nontrivial new results related to the original graph dimension are subsequently deduced from our study of universal dimension, including chromatic properties, extremal properties and a disproof of two conjectures of Felsner and Trotter.

Information

Type
Paper
Copyright
2005 Cambridge University Press