fractionally coloring the plane

The fractional chromatic number of the plane is at least 105/29

We actually wrote down the proof for 76/21, but at the end of section 3 we show how to improve this to 105/29, it complicates the discharging with a few more phases.  This is the limit of our method because any larger value and we can't prove that a maximum weight independent set has to intersect the core in a maximal independent set in the triangular lattice.

Here are the pretty pictures.

How to win at solitaire when a demon is mucking with the cards.

A slightly simpler proof of Kostochka's lemma. It avoids the need for one extra lemma.

For a collection of maximum cliques Q in a graph G, let X_Q be the
intersection graph of Q.

Lemma. If Q is a collection of maximum cliques in a graph G with
\omega(G) > 2/3 (\Delta(G) + 1) such that X_Q is connected, then \cap
Q \neq \emptyset.

Proof. Suppose not and choose a counterexample Q := {Q_1, ..., Q_r}
minimizing r.

Let A be a noncutvertex in X_Q and B a neighbor of A. Put Z := Q -
{A}. Then X_Z is connected and hence by minimality of r, \cap Z \neq
\emptyset. In particular, |\cup Z| \leq \Delta(G) + 1.

Hence |\cup Q| \leq |\cup Z| + |A - B| \leq 2(\Delta(G) + 1) -
\omega(G) < 2\omega(G). This contradicts Hajnal's lemma.

Conjecture 14 from my recent paper is false by some pretty easy examples.


However, i still think Conjecture 13 (which Conjecture 14 implies) is true.

See more at Interesting Graphs.

The only 7-mule containing a K_7 minus an edge.

i proved this recently. It would be interesting to explicitly construct a sequence of graphs showing that t_0 does not exist instead of relying on P \neq NP.

Here is a much simpler proof of a lemma of Kostochka that i translated from Russian and used.

Lemma. Let G be a graph with omega > 2/3 (Delta + 1). If Q is a collection of maximum cliques in G such that X_Q is connected, then \cap Q \neq \emptyset.

Proof. Assume not and let Q = {Q_1, ..., Q_r} be a bad collection of maximum cliques with r minimal. Then r \geq 3 and X_Q is complete since it is connected and transitive. Put Z = Q - {Q_1}. Then X_Z is connected and hence by minimality \cup Z contains a universal vertex. In particular |\cup Z| \leq Delta + 1. Thus

|\cup Q| \leq |Q_1 - Q_2| + |\cup Z| \leq 2(Delta + 1) - omega < 2omega.

But then Hajnal gives a contradiction.

Working on using the following theorem to prove the full Borodin-Kostochka conjecture.

Theorem: If G contains a doubly critical edge and satisfies chi >= Delta >= 6, then G contains a K_Delta.

So, the Borodin-Kostochka conjecture (and more) holds for graphs containing a doubly critical edge. This allows one to try to find a doubly critical edge instead of trying to find a big clique. This works to give a new proof of Brooks' theorem, but it gets intricate for the Borodin-Kostochka condition; however, there is a lot of room to play and it looks very promising (this all uses a decomposition theorem of Lovasz -- actually a modification of it by Catlin).

nqsiq

dxbpgril