Name
Abstract | ||
|---|---|---|
A result of Haxell (Graphs Comb 11:245---248, 1995) is that if $$G$$G is a graph of maximal degree $$\\Delta $$Δ, and its vertex set is partitioned into sets $$V_i$$Vi of size $$2\\Delta $$2Δ, then there exists an independent system of representatives (ISR), namely an independent set in the graph consisting of one vertex from each $$V_i$$Vi. Aharoni and Berger (Trans Am Math Soc 358:4895---4917, 2006) generalized this result to matroids: if a matroid $$\\mathcal {M}$$M and a graph $$G$$G with maximal degree $$\\Delta $$Δ share the same vertex set, and if there exist $$2\\Delta $$2Δ disjoint bases of $$\\mathcal {M}$$M, then there exists a base of $$\\mathcal {M}$$M that is independent in $$G$$G. In the Haxell result the matroid is a partition matroid. In that case, a well known conjecture, the strong coloring conjecture, is that in fact there is a partition into ISRs. This conjecture extends to the matroidal case: under the conditions above there exist $$2\\Delta (G)$$2Δ(G) disjoint $$G$$G-independent bases. In this paper we make a modest step: proving that for $$\\Delta \\ge 3$$Δ¿3, under this condition there exist two disjoint $$G$$G-independent bases. The proof is topological. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s00373-014-1439-8 | Graphs and Combinatorics |
Keywords | Field | DocType |
Independent systems of representatives, Disjoint bases of matroids, Strong coloring conjecture, 05B35, 05B40, 05C69 | Matroid,Topology,Discrete mathematics,Graph,Combinatorics,Disjoint sets,Vertex (geometry),Independent set,Strong coloring,Partition (number theory),Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 5 | 1435-5914 |
Citations | PageRank | References |
0 | 0.34 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ron Aharoni | 1 | 380 | 66.56 |
| Eli Berger | 2 | 182 | 52.72 |
| Philipp Sprüssel | 3 | 46 | 8.52 |