Binary matroid conjecture excluding an independent set and a triangle

Let ss be a positive integer. A simple binary matroid is a binary matroid with no loops or parallel elements; an induced IsI_s-restriction and an induced PG(1,2)\operatorname{PG}(1,2)-restriction are restrictions isomorphic to the indicated matroids. Write χ(M)\chi(M) for the chromatic number of a matroid MM. Binary matroid chromatic-number conjecture. For every s1s \ge 1, there exists an integer kk such that if MM is a simple binary matroid with no induced IsI_s-restriction or PG(1,2)\operatorname{PG}(1,2)-restriction, then

χ(M)k.\chi(M) \le k.

This is the t=2t=2 case of the proposed matroidal analogue of the Gyárfás–Sumner conjecture. The corresponding general matroidal statement is refuted already when s=t=3s=t=3, while this triangle-excluding case remains open; its graph-theoretic analogue is known for stars but open in general.

Sources & referencesView supporting material

Primary source

Marthe Bonamy, Frantisek Kardos, Tom Kelly, Peter Nelson and Luke Postle, “The structure of binary matroids with no induced claw or Fano plane restriction”, arXiv:1806.04188 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.