4
$\begingroup$

I have found an interesting exercise in my introduction to graphs workbook:

Let $ad(G) = \frac{2\vert E(G)\vert}{\vert V(G) \vert}$ and $mad(G) = max\{ad(H): H\ is\ an\ induced\ subgraph\ of\ G\}$.

Given a graph $G$ and a number $k \geq 3$, prove that if $\chi(G) > k \wedge mad(G) \leq k \Rightarrow \exists A \subseteq V(G)$ such that $[A]_{G}$ is $k - regular$.

I believe this can proved by contradiction:

Given a $G$ and $k$ for which the properties hold, we assume that $G$ has no induced subgraph $H$ that is $k - regular$. We then prove that if $\nexists H$ then at least one of the property is false and thus we contradict ourselves however I can't quite figure out the connection between $H$ and the mentioned properties.

How would you go about solving this?

$\endgroup$
1
  • $\begingroup$ I don't know what $\chi_G$ is. In any case, please edit your title to be less mathy and more readable (and searchable!). $\endgroup$
    – Raphael
    Nov 5 '13 at 17:06
3
$\begingroup$

Hint: It's better to prove that if $mad(G) \leq k$ and no induced subgraph of $G$ is $k$-regular then $\chi(G) \leq k$. Here is the idea of the proof:

  1. Show that $G$ has a vertex $v$ of degree smaller than $k$.
  2. Color $G - v$ using $k$ colors (by induction).
  3. Complete this to a $k$-coloring of $G$.
$\endgroup$

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.