No coin nor oath required. For personal study only.
Two examples in graph theory of the concept of the maximum and minimum pair of invariants resulting from a graphical parameter are ( I ) the chromatic number and its maximum version, the achromatic number, and (2) the genus and the maximum genus. The primary purpose of this expository survey is to propose the generalization of this idea to each invariant p of a maximum or minimum nature. As illustrations, we consider for p the number of independent points or lines, the point arboricity, the connectivity, the rectilinear crossing number, the diameter of a spanning tree, and the conventional extremal number with respect to a forbidden subgraph. An additional objective is to describe the idea of an "interpolating invariant" which takes on, in a precise sense, all values between its minimum and its maximum, and to give examples.
The chromatic number x of a graph G is one of the most intensively studied invariants of graph theory. In its usual formulation, x(G) is the minimum number of colors which can be assigned to the points of G so that no two points of the same color are adjacent. A well-known alternative statement defines x(G) as the minimum n such that there is a complete n-coloring of G (homomorphism of G onto the complete graph K,,). On replacing minimum by maximum in this alternative definition, one is led as in [ 131 to the discovery of the achromatic number $. The interpolation theorem for graphical homomorphisms is now stated.
Theorem A [14]. For any graph G and for each n between x(G) and $(G), there exists a homomorphism of G onto K,,.
๐ SIMILAR VOLUMES
We consider generalizations of the Tutte polynomial on multigraphs obtained by keeping the main recurrence relation T(G)=T(Gรe)+T(G&e) for e # E(G) neither a bridge nor a loop and dropping the relations for bridges and loops. Our first aim is to find the universal invariant satisfying these conditio
Topp, J., Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices, Discrete Mathematics 12 1 (1993) 199-210. A set I of vertices of a graph G is an independent set if no two vertices of I are adjacent. A set M of edges of G is an edge dominating s
Negami has introduced two polynomials for graphs and proved a number of properties of them. In this note, it is shown that these polynomials are intimately related to the well-known Tutte polynomial. This fact is used, together with a result of Brylawski, to answer a question of Negami. The matroid