A blow-up construction and graph coloring

DOI10.1016/0012-365X(94)00051-JzbMATH Open0835.05024arXivalg-geom/9401007OpenAlexW3103925361WikidataQ60145534 ScholiaQ60145534MaRDI QIDQ1901028FDOQ1901028

Authors: Paolo Aluffi 

Publication date: 22 April 1996

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/alg-geom/9401007

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

zbMATH Keywords

graph coloringchromatic polynomial

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15)

Cites Work

• The Tutte polynomial
• Title not available (Why is that?)
• Every planar map is four colorable. II: Reducibility
• Theory of Matroids
• Title not available (Why is that?)
• Title not available (Why is that?)
• Modular elements of geometric lattices
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (1)

• Euler characteristics and chromatic polynomials

Uses Software

• schubert

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)