chromatic number

色数

Combinatorics · Undergraduate · Mathematics Resources editorial compilation (AI-assisted)

Other names / variants: vertex chromatic number

Translation evidence: Literature usage

Meaning in context

The chromatic number χ(G) of a finite simple graph is the least nonnegative integer k admitting a vertex coloring with k colors in which adjacent vertices receive different colors.

有限简单图的色数 χ(G) 是允许相邻顶点颜色不同的顶点着色所需的最少颜色数；本记录允许零个颜色用于空图。

Example

χ(C5)=3\chi(C_5)=3, whereas χ(C4)=2\chi(C_4)=2.

Usage and distinctions

This counts vertex colors, not edge colors; an arbitrary Ramsey edge coloring has no proper-coloring requirement.

Read the encyclopedia explanation

Recommended reading in this subject · Preparation & skip guidance

Definition sources

  1. Joy Morris — Combinatorics, version 2.1.1Section 14.3, Definitions 14.3.2–14.3.3 and Notation 14.3.4 · Checked 2026-10-14

Translation sources

  1. 新疆大学 — 本科课程教学大纲汇编，图论（050762）PDF p.95 / printed p.94，图论课程第三部分，第八章「顶点着色」内容中的「色数」 · Checked 2026-10-14
Edit source / propose a PRReport a correction

Original encyclopedia and terminology content: CC BY-SA 4.0. Contribute or report a correction.