1
$\begingroup$

So I have an exam coming up, my review sheet has a few questions on critical graph. Can I have some help with these questions please?

Definitions: A subgraph $H$ of $G$ is a $\underline{critical \ subgraph}$ if $\chi(G)=\chi(H)$ but removing any edge or vertex from $H$ results in a graph with lower chromatic number. A graph is $\underline{critical}$ if it's a critical subgraph for some graph.

(1) Suppose $H$ is a critical graph with $\chi(H)=4$. How many vertices of degree 1 can $H$ have. Explain. How many vertices of degree $2$?

(2) Suppose $H$ is a critical graph with $\chi(H)=5$. How many vertices of degree 2 can $H$ have. Explain. How many vertices of degree $3$?

(3) Generalize the previous two questions. That is if $H$ is critical what's the relation between $\chi(H)$ and minimum degree $H$?

For (1) and (2) do I add on new vertices and show that these vertices can be colored using any of the k colors other that the colors used by its neighbors? Or...

(1) and (2) this is not possible (I think) because the minimal degree of a critical graph seems to be at least k-1?

$\endgroup$
3
$\begingroup$

If $‎\chi‎ (H)=k$, then $‎\delta‎ (H)‎\geq‎‎ k-1$.

Because if there exists a vertex $v$ such that $d(v)<k-1$, then we can remove the vertex $v$ and from criticality we can color vertices by $k-1$ colors. But for $v$ we have at least one color. So we can color $H$ by $k-1$ colors, a contradiction.

So in general we have $\delta‎ (H)‎‎\geq‎ \chi‎ (H)-1$

$\endgroup$
2
  • $\begingroup$ Thanks. So I was pretty close with my reasoning? $\endgroup$ Feb 26 '17 at 23:28
  • $\begingroup$ Yes. You were right. I just explain your idea in a complete way. $\endgroup$ Mar 2 '17 at 22:56

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.