4
$\begingroup$

Given any poset $(P,\leq)$ we define the "direct neighbor graph" as follows. Let $$E_P = \big\{\{a,b\}: (a<b \text{ or } a>b) \text{ and } \; ]\min\{a,b\},\max\{a,b\}[ = \emptyset\big\}.$$ It is easy to see the $(P,E_P)$ is a simple undirected graph that can contain a $3$-clique, but not a $4$-clique. But can $\chi(P,E_P)$ become arbitrarily large?

EDIT. Peter Taylor points out that my remark on $3$-cliques is wrong - sorry about that.

$\endgroup$
3
  • $\begingroup$ Your "direct neighbour graph" looks like the transitive reduction, but I'm not sure how it could contain a 3-clique. $\endgroup$ Oct 11 '17 at 14:16
  • $\begingroup$ Right @PeterTaylor - it can't...! If it cannot contain an odd cycle, then the answer is clear. Sorry for my mistake $\endgroup$ Oct 11 '17 at 14:35
  • 2
    $\begingroup$ It can contain an odd cycle. Consider a poset which is fully characterised by two chains: $a < b < c$ and $a < d < e < c$. Then $(P, E_P)$ is a single cycle of length 5. $\endgroup$ Oct 11 '17 at 14:50
3
$\begingroup$

Yes, the chromatic number of a Hasse diagram can be arbitrarily large. Bollobás shows in the following article that for any $k$ there exists a finite lattice whose Hasse diagram is not $k$-colorable.

MR505730 05C15 (06A20) 
Bollobás, Béla Colouring lattices. Algebra Universalis 7 (1977), no. 3, 313–314.

Here are a few other papers that solve the problem, but I have not been able to find any freely available paper.

MR748915 05A17 (06B99 06D99) 
Nešetřil, Jaroslav; Rödl, Vojtěch Combinatorial partitions of finite posets and lattices—Ramsey lattices. Algebra Universalis 19 (1984), no. 1, 106–119.

MR1129613 05C15 (06A07) 
Kříž, Igor; Nešetřil, Jaroslav Chromatic number of Hasse diagrams, eyebrows and dimension. Order 8 (1991), no. 1, 41–48.
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.