Show that $\chi(G)=\omega(G)$

Question

Let $(X,<)$ be a poset and $G$ a graph with vertex set $X$. Let $E(G)=\{\{u,v\}: u,v \in X\ \text{and}\ u<v\}$. Show that $\chi(G)=\omega(G)$.

$\chi(G)$ is the chromatic number of $G$.

$\omega(G)$ is the number of the vertices in the maximum clique size in $G$.

I don't understand how it is possible to build a partially ordered set with ''$<$'' symbol.

and what does the edge set look like? For me it is always a complete graph.

Answer 1

It seems that you are unfamiliar with the concept of partially ordered sets. Luckily there is a lot of information about them readily available on the internet; see for instance Wikipedia.

Here is a brief overview. A relation $\leq$ on a set $X$ is called a partial order if it satisfies the following three criteria:

1. For all $x\in X$ we have $x \leq x$ (reflexivity);
2. If $x \leq y$ and $y \leq x$, then $x = y$ (antisymmetry);
3. If $x \leq y$ and $y \leq z$, then $x \leq z$ (transitivity).

Given a partial order $\leq$ we define its corresponding strict partial order $<$ by declaring that $a < b$ iff $a \leq b \wedge a \neq b$. (Conversely, given a strict partial order $\prec$ we may define the corresponding non-strict partial order $\preceq$ by declaring that $x \preceq y$ iff $x \prec y \vee x = y$.)

This is all very abstract; it helps to see some examples.

• The usual order $\leq$ on the real numbers is a partial order. By restriction, this also orders any subset of $\mathbb{R}$ we may want to consider (in particular $\mathbb{N}$, $\mathbb{Z}$ and $\mathbb{Q}$).
• A different partial order on $\mathbb{N}^+$ is provided by the divisibility relation: we define $n \preceq m$ to mean $m$ is divisible by $n$. It is readily verified that this meets the criteria from the definition. However, now the associated comparability graph is no longer complete: we have $2 \not\preceq 3$ as well as $3 \not\preceq 2$, so there is no edge between $2$ and $3$. We say that $2$ and $3$ are incomparable.
• A very natural one: for any set $X$, the power set $\mathcal P(X)$ is ordered by inclusion (denoted $\subseteq$). Again, there are many pairs of incomparable elements in this case (provided $|X| \geq 2$). For instance, if $A,B\subseteq X$ are disjoint subsets of $X$, then we have $A \not\subseteq B$ and $B \not \subseteq A$. (But $A$ and $B$ need not be disjoint to be incomparable.)
• We may equip any set $X$ with the trivial order: $x \leq y$ if and only if $x = y$. Now the comparability graph has no edges at all.
• Wikipedia provides a few other examples of partial orders.

In your exercise, you are given a partial order on a (finite) set, but you don't know which one it is. It might be complete, it might be trivial, but it's probably something in between. Nevertheless, this turns out to be enough to prove that the chromatic number and the clique number coincide.

Good luck!