Abstract: Given a graph G (or more generally a matroid embedded in a projective space), we construct a sequence of varieties whose geometry encodes combinatorial information about G. For example, the chromatic polynomial of G (giving at each m>0 the number of colorings of G with m colors, such that no adjacent vertices are assigned the same color) can be computed as an intersection product between certain classes on these varieties, and other information such as Crapo's invariant find a very natural geometric counterpart. The note presents this construction, and gives `geometric' proofs of a number of standard combinatorial results on the chromatic polynomial.
Recommendations
- On constructive methods in the theory of colour-critical graphs
- scientific article; zbMATH DE number 1052826
- Sur le coloriage des graphs
- The coloring graph of complete graphs
- A NOTE ON COLOURING OF COMPLETE GRAPHS
- The coloring of graphs
- scientific article; zbMATH DE number 798646
- On the construction of cograph color critical graphs
- scientific article; zbMATH DE number 1309148
- Extremal graphs in some coloring problems
Cites work
- scientific article; zbMATH DE number 4016785 (Why is no real title available?)
- scientific article; zbMATH DE number 431811 (Why is no real title available?)
- scientific article; zbMATH DE number 3859276 (Why is no real title available?)
- scientific article; zbMATH DE number 671731 (Why is no real title available?)
- scientific article; zbMATH DE number 3342868 (Why is no real title available?)
- Every planar map is four colorable. II: Reducibility
- Modular elements of geometric lattices
- The Tutte polynomial
- Theory of Matroids
This page was built for publication: A blow-up construction and graph coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1901028)
