On the heterochromatic number of hypergraphs associated to geometric graphs and to matroids

Details On the heterochromatic number of hypergraphs associated to geometric graphs and to matroids On the heterochromatic number of hypergraphs associated to geometric graphs and to matroids

2010-11-22

arxiv.org/abs/1011.4888v1

Mathematics

Combinatorics

Scientific paper

The heterochromatic number hc(H) of a non-empty hypergraph H is the smallest integer k such that for every colouring of the vertices of H with exactly k colours, there is a hyperedge of H all of whose vertices have different colours. We denote by nu(H) the number of vertices of H and by tau(H) the size of the smallest set containing at least two vertices of each hyperedge of H. For a complete geometric graph G with n > 2 vertices let H = H(G) be the hypergraph whose vertices are the edges of G and whose hyperedges are the edge sets of plane spanning trees of G. We prove that if G has at most one interior vertex, then hc(H) = nu(H) - tau(H) + 2. We also show that hc(H) = nu(H) - tau(H) + 2 whenever H is a hypergraph with vertex set and hyperedge set given by the ground set and the bases of a matroid, respectively.

Affiliated with

Also associated with

No associations

Rating

On the heterochromatic number of hypergraphs associated to geometric graphs and to matroids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the heterochromatic number of hypergraphs associated to geometric graphs and to matroids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the heterochromatic number of hypergraphs associated to geometric graphs and to matroids will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-657999