Skip to main content
MathOverflow

Return to Question

Removed deprecated (discrete-mathematics) tag - see the tag info: https://mathoverflow.net/tags/discrete-mathematics/info
Link
edit approved Aug 12, 2017 at 6:02
Martin Sleziak
edit approved Aug 12, 2017 at 6:02
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40
Post Closed as "Not suitable for this site" by Douglas Zare, Ben Barber, Jan-Christoph Schlage-Puchta, R.P., Neil Strickland
added 40 characters in body
Source Link
Jan-Christoph Schlage-Puchta
Jan-Christoph Schlage-Puchta
  • 9.2k
  • 2
  • 30
  • 56

I need this proof:

Let G$G$ be a graph such that χ (H) <χ (G)$\chi (H) <\chi (G)$ for every subgraph H$H$ of G. (a$G$. A graph thusis called k$k$-critical, if χin addition (G) = k)$\chi (G) = k$. Prove that χ (G) ≤ δ + 1$\chi (G) ≤ \delta + 1$.

I need this proof:

Let G be a graph such that χ (H) <χ (G) for every subgraph H of G. (a graph thus called k-critical, if χ (G) = k). Prove that χ (G) ≤ δ + 1

I need this proof:

Let $G$ be a graph such that $\chi (H) <\chi (G)$ for every subgraph $H$ of $G$. A graph is called $k$-critical, if in addition $\chi (G) = k$. Prove that $\chi (G) ≤ \delta + 1$.

Source Link
dantopa
dantopa
  • 7
  • 2

Graph Coloring Proof χ (G) ≤ δ + 1 for k-criticals

I need this proof:

Let G be a graph such that χ (H) <χ (G) for every subgraph H of G. (a graph thus called k-critical, if χ (G) = k). Prove that χ (G) ≤ δ + 1