Хроматические свойства соединения дерева и нулевого графа | Прикладная дискретная математика. 2020. № 50. DOI: 10.17223/20710410/50/7

Изучаются хроматические свойства графа G, который является объединением дерева T_p и нулевого графа O_q. Докажем, что G хроматически уникален тогда и только тогда, когда 1 ≤ p ≤ 3, 1 ≤ q ≤ 2; граф H и T_p + O_p-1 и χ-эквивалентны тогда и только тогда, когда H = T′_p + O_p-1,где T′_p дерево порядка p; H и T_p + O_p are χ-эквивалентны тогда и только тогда, когда H ∈ {T′_p + O_p, T″_p+1 + O_p-1}, where T′_p дерево порядка p, T″_p+1 дерево порядка p + 1. Мы также докажем, что если p ≤ q, тогда χ′(G) = ch′(G) = ∆(G); if ∆(G) = |V(G)| - 1, то χ′(G) = ch′(G) = ∆(G) тогда и только тогда, когда G ≠ K₃.