Yes; in fact, for most graphs, the difference is very large.

Consider the random graph on $n$ vertices: for every edge, we flip an independent fair coin to determine if that edge is present or not.

Then for large $n$, the clique number is almost always close to $2\log_2 n$. Proving that it is actually often this high is tricky, so I'll just prove that it usually does not go higher.

The probability that a set of $k$ vertices forms a clique is $2^{-\binom k2}$, and there are $\binom nk$ sets of $k$ vertices, so the expected number of cliques of order $k$ is $\binom nk 2^{-\binom k2}$, which is very approximately $n^k 2^{-k^2/2}$. When we set $k = 2\log_2 n$, $n^k 2^{-k^2/2} = 1$, and the actual expected number of cliques (without the approximation) is going to $0$ as $n \to \infty$. This means that the probability of having even a single clique on more than $2\log_2 n$ vertices is also going to $0$ as $n \to \infty$.

Meanwhile, there is a different obstacle to having a small chromatic number: the inequality $\chi(G) \ge \frac{n}{\alpha(G)}$, where $\alpha(G)$ is the independence number of $G$. By the same argument as for cliques, the largest independent set in $G$ (the largest set of vertices with no edges between them) also almost never exceeds $2 \log_2 n$. Well, in a proper coloring of $G$, every color must induce an independent set. Therefore for almost all $G$, no color has more than $2\log_2 n$ vertices, and therefore at least $\frac{n}{2\log_2 n}$ colors are needed.

(This is actually a good estimate of the chromatic number of the random graph but, again, the reverse bound is very hard to prove; it was shown by Bollobás in 1988.)

So with probability close to $1$ for a random graph, and therefore for almost all $n$-vertex graphs, the clique number and chromatic number are very far apart: the former is less than $2\log_2 n$ and the latter is more than $\frac{n}{2\log_2 n}$.

You are right, if $\Delta(G)>2$ and all cycles of $G$ are odd then $\chi'(G)=\Delta(G)$.

You can prove this by induction on the number of cycles in $G$. We my assume $G$ is connected, since if it is true for every connected graph we can just colour components separately.

If $G$ has no cycles then it is a tree. Root it at any vertex, and colour edges one by one in order of distance from the root. We can do this using a greedy algorithm with $\Delta$ colours: when we colour an edge, the only incident edges we have previously coloured all meet it at the same endpoint, so there are at most $\Delta-1$ forbidden colours.

If there is exactly one cycle, then we can do the same thing. First, colour the cycle with $3\leq \Delta$ colours. Now colour the other edges in order of distance from the cycle; the same argument works.

If there are two or more cycles, choose two and call them $C_1,C_2$. If they have a vertex $v$ in common, note that there can be no path between the cycles that does not go through $v$, since if there is such a path $P$ we could construct a cycle by going along $P$, round $C_2$ to $v$, and round $C_1$ to the start of $P$. Since both cycles are odd, and we can choose which direction to go round them, we can make this new cycle of either parity, a contradiction. Thus $v$ is a cutvertex, and we can find two graphs $G_1,G_2$, with no common edges and no common vertices other than $v$, such that $G$ is obtained by gluing $G_1$ and $G_2$ together at $v$, and each containing one of the cycles. By induction, we can define two colourings $c_1,c_2$ of $G_1,G_2$ respectively, each with colours from $\{1,...,\Delta(G)\}$. Since $\Delta(G)\geq d_G(v)$ we can reorder the colours for $c_2$, if necessary, so that the set of colours used at $v$ by $c_2$ is disjoint from those used at $v$ by $c_1$.

If $C_1,C_2$ do not have a vertex in common, then by a similar argument there cannot be two vertex-disjoint paths between them (otherwise there would be cycles of either parity using these paths and part of $C_1,C_2$). This means, via Menger's theorem, that there is a single vertex $v$ such that all paths between them go through $v$, and now you can do the same thing.

## Best Answer

Any Graph $G=(V, E)$ can be extended to a graph $G\prime=(V\prime, E\prime)$ satisfying $w(G\prime)=\chi(G\prime)$, simply by adding to $G$ a clique of size $\chi(G)$, disjoint from $V$.

But there are actually a bunch of graph classes ensuring this equality. For examples: bipartite graphs, comparability graphs, chordal graphs...

I refer to the book by Alexander Schrijver "Combinatorial Optimization" Chapter 65 & 66.