scientific article; zbMATH DE number 1161251

Publication date 10 December 1998

chromatic number dimension Hamiltonian cycles and paths hypergraph coloring linear extension planar graphs poset Ramsey theory random graph random poset

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Generalized Ramsey theory (05C55) Combinatorics of partially ordered sets (06A07)

Review text

In this survey article the author discusses in adequate detail for even a student entering the field a number of questions whose answers, partial and complete, form significant and rapidly growing subareas of a theory of ``diagrams, where in this case a ``diagram is a pair \((G,\text{P})\), with \(G=\)(V, E) a graph and \(P=\)(X, P) a poset which are in some sense related to one another. For example, when for Hasse diagrams the relationship runs from posets to graphs, in incidence posets the relationship runs in the opposite direction, while in both situations the entity under consideration involves both. Clearly, it is possible to define many diagram ``types, and for each such type it is usually interesting to investigate how classes of posets are related to classes of graphs. E.g., Schyder's theorem states that a graph \(G\) is planar iff the dimension of its incidence poset is at most 3. In reality this is not a theorem about graphs nor a theorem about posets, even though it is significant in both settings. The author's early interest in graph theory and his later work in poset-combinatorics marks him as certainly a diagram-theorist also, along with a large number of others who are recognizable as working in an area one early prophet of which has been I. Rival (leaving the Erdős universal set unclassified). Given the number of results, statements, conjectures listed, it is not useful to attempt to copy them here other than to emphasize that if one is lacking for ideas but interested in participating in the development of what is bound to become quite a wide reaching useful branch of the mathematics tree, there is still time to do so and using this article along with subsequent literature as guide, an opportunity to succeed as well. Topics covered include planar graphs, Hamiltonian cycles and paths, graph and hypergraph coloring, on-line algorithms, intersection graphs, inclusion orders, random methods and Ramsey theory among others.

Recommendations

Cited in

(16)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4393243)