Trong Lý thuyết đồ thị, tô màu đồ thị (tiếng Anh: graph coloring) là trường hợp đặc biệt của gán nhãn đồ thị, mà trong đó mỗi đỉnh hay mỗi cạnh hay mỗi miền của đồ thị có thể được gán bởi một màu hay một tập hợp các màu nào đó. Tô màu đồ thị có thể là:Sắc số (tiếng Anh: chromatic number) của một đồ thị là số màu ít nhất để tô các đỉnh.Sắc số của đồ thị G được ký hiệu là χ(G).Số màu cạnh (tiếng Anh: chromatic index) của một đồ thị là số màu ít nhất dùng để tô các cạnh. Số màu cạnh của đồ thị G được ký hiệu là χ'(G).Số màu cạnh của đồ thị G bất kì bằng sắc số của đồ thị đường L((G)) của đồ thị đó:do đó việc nghiên cứu tô màu cạnh của G tương đương với nghiên cứu tô màu đỉnh của L(G).