6
$\begingroup$

Show that if $G$ is a loopless graph, $k≥1$ is an integer and $χ(G) > k$ then $G$ has a path with $k$ edges.

So, we can assume WLOG that $G$ is connected. we're looking for a path $P$ where $|V(P)| = k+1 $ and $|E(P)| = k.$ I'm stuck with this question. I know that $χ(G) < d(G) + 1$ where $d(G)$ is the maximum vertex degree of $G$. If $χ(G)= k+1$ , then there must be at least $k+1$ vertices of degree $> k$. I'm not sure how to take it from there, or if I'm even in the right direction. Can anyone please help??

  • 1
    Please do not change the question you have asked. If you want, you can ask another question. It is extremely confusing to alter a question to which an answer has already been provided.2012-11-24

3 Answers 3

3

Let $\ell$ denote the length of the longest path in $G$ with chromatic number $\chi > k$. The minimal degree of $G$ satisfies $\delta \ge \chi - 1 \ge k$ and the longest path satisfies $\ell \ge \delta$. Therefore $\ell \ge k$.

Edit: I made a small mistake in the above, but the idea is the same. Let $G$ be a $\chi$-chromatic graph where $ \chi > k$. Then $G$ contains a $\chi$-critical subgraph $H\subseteq G$. For the $\chi$-critical graph $H$, we have $\delta_H \ge \chi - 1$ where $\delta_H$ is the smallest vertex degree of $H$.

We know that a graph with least degree $\delta$ necessarily has a path of length at least $\delta$ so it follows that the longest path of $H$ is of length at least $\delta_H \ge \chi - 1 \ge k$ So $H$ contains a path of length at least $k$ and therefore $G$ also contains the same path.

  • 0
    Take a look at section $14.2$ in this [book](http://books.google.ca/books?id=HuDFMwZOwcsC&pg=PA361&source=gbs_toc_r&cad=4#v=onepage&q&f=false)2012-11-17
1

We know that any chromatic coloring can be made into Grundy coloring (Grundy k-coloring is a proper k-coloring in which for any i=2,3...,k each vertex receiving color i has a neighbor in a vertex which receives color j, for all j

  • 0
    In a Grundy coloring, each vertex assigned color $i$ has neighbors of size $1,2,\dots, i-1$. (The stronger condition you're asking for is not possible, in general.) Then, of course, we can start at any vertex of color $k$ and draw a path, stepping from color $i$ to $i-1$ at each step.2017-11-16
1

Give $G$ an acyclic orientation. For each vertex $v$ let $f(v)$ be the length of the longest directed path from $v.$ Clearly, if $uv$ is a directed edge, then $f(u)\ge1+f(v)\gt f(v).$ Therefore $f$ is a proper coloring. Since $\chi(G)\gt k,$ and the values of $f$ are nonnegative integers, there must be a vertex $v$ with $f(v)\ge k;$ i.e., there is a directed path from $v$ of length at least $k.$