Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-23T13:38:49.270Z Has data issue: false hasContentIssue false
  • English
  • Français

Homomorphism and Dimension

Published online by Cambridge University Press:  11 October 2005

PATRICE OSSONA de MENDEZ  and
PIERRE ROSENSTIEHL
PATRICE OSSONA de MENDEZ
Affiliation:
Centre d'Analyse et de Mathématiques Sociales, CNRS, UMR 8557, 54 Bd Raspail, 75006 Paris, France (e-mail: [email protected], [email protected])
PIERRE ROSENSTIEHL
Affiliation:
Centre d'Analyse et de Mathématiques Sociales, CNRS, UMR 8557, 54 Bd Raspail, 75006 Paris, France (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 14 , Issue 5-6 , November 2005 , pp. 861 - 872
Copyright
2005 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)