… Три ребра e 1 , e 2 і e 3 у графі G = (V, E) називаються послідовними, якщо вони утворюють шлях або цикл довжиною 3. Розфарбування країв G називається 3-послідовним фарбуванням ребер, якщо для будь-яких 3-послідовних ребер e 1 , e 2 та e 3 , ребро e 2 отримує колір e 1 або e 3 .
3-послідовне число розфарбовування ребер графа G, ψ 3c (G), максимальна кількість кольорів 3-послідовного фарбування країв G. Це поняття було введено та детально досліджено в [3], де доведено, що визначення 3-послідовного числа розфарбовування ребер для довільних графів є NP-важким. …
Прикладом задачі 3-розфарбування є неорієнтований граф G (V, E), і завдання полягає в тому, щоб перевірити, чи існує можливе призначення кольорів для кожної з вершин V, використовуючи лише 3 різні кольори з кожним сусідом різного кольору.
У теорії графів правильним розфарбуванням ребер графа є призначення «кольорів» ребрам графа, щоб жодні інцидентні ребра не мали однакового кольору. Наприклад, на малюнку праворуч показано розфарбування ребер графа червоним, синім і зеленим кольорами.
Петерсен представив найвідоміший граф, граф Петерсена, як приклад кубічного графа без мостів, який не розфарбовується за Тейтом, тобто є не можна розфарбовувати по 3 краях.
Відповідь і пояснення: Послідовні вершини многокутника є будь-які дві вершини, з’єднані однією стороною.