Граф ходів короля
Граф ходів короля 8 × 8
Вершин	nm
Ребер	4nm - 3(n + m) + 2
Обхват	${\displaystyle 3}$ якщо ${\displaystyle \min(m,n)>1}$
Хроматичне число	${\displaystyle 4}$ when ${\displaystyle \min(m,n)>1}$
Хроматичний індекс	${\displaystyle 8}$ when ${\displaystyle \min(m,n)>2}$

У теорії графів граф ходів короля — граф, що зображує всі можливі ходи короля на шахівниці; кожна вершина відповідає клітинці на дошці, а ребра відповідають можливим ходам.

Для графа ходів короля на дошці розміру ${\displaystyle n\times m}$ число вершин дорівнює ${\displaystyle nm}$. Для дошки ${\displaystyle n\times n}$ число вершин дорівнює ${\displaystyle n^{2}}$, а число ребер дорівнює ${\displaystyle (2n-2)(2n-1)}$.

Окіл вершини в графі ходів короля відповідає околу Мура клітинного автомата^[1]. Узагальнення графа ходів короля можна отримати з рамкового графа (плоского графа, в якого кожна грань є чотирикутником і кожна внутрішня вершина має принаймні чотири сусіди), додавши для кожної чотирикутної грані дві діагоналі^[2].

• Граф ходів коня
• Граф решітки
• Туровий граф

•   Портал «Шахи»