Coloring $Δ$-Critical Graphs With Small High Vertex Cliques

Details Coloring $Δ$-Critical Graphs With Small High Vertex Cliques Coloring $Δ$-Critical Graphs With Small High Vertex Cliques

2011-02-04

arxiv.org/abs/1102.1023v1

Mathematics

Combinatorics

Scientific paper

We prove that $K_{\chi(G)}$ is the only critical graph $G$ with $\chi(G) \geq
\Delta(G) \geq 6$ and $\omega(\mathcal{H}(G)) \leq \left \lfloor
\frac{\Delta(G)}{2} \right \rfloor - 2$. Here $\mathcal{H}(G)$ is the subgraph
of $G$ induced on the vertices of degree at least $\chi(G)$. Setting
$\omega(\mathcal{H}(G)) = 1$ proves a conjecture of Kierstead and Kostochka.

Affiliated with

Also associated with

No associations

Rating

Coloring $Δ$-Critical Graphs With Small High Vertex Cliques does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Coloring $Δ$-Critical Graphs With Small High Vertex Cliques, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coloring $Δ$-Critical Graphs With Small High Vertex Cliques will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-52360