RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика // Архив

ПДМ, 2020, номер 50, страницы 93–101 (Mi pdm725)

Прикладная теория графов

The chromaticity of the join of tree and null graph

L. X. Hung

HaNoi University for Natural Resources and Environment, Ha Noi, Viet Nam

Аннотация: The chromaticity of the graph $G$, which is join of the tree $T_p$ and the null graph $O_q$, is studied. We prove that $G$ is chromatically unique if and only if $1\le p\le 3$, $1\le q\le 2$; a graph $H$ and $T_p+O_{p-1}$ are $\chi $-equivalent if and only if $H=T^\prime _p+O_{p-1}$, where $T^\prime _p$ is a tree of order $p$; $H$ and $T_p+O_p$ are $\chi $-equivalent if and only if $H\in \{T^\prime _p+O_p, T^{\prime \prime }_{p+1}+O_{p-1}\}$, where $T^\prime _p$ is a tree of order $p$, $T^{\prime \prime }_{p+1}$ is a tree of order $p+1$. We also prove that if $p\le q$, then $\chi ^\prime (G)=ch^\prime (G)=\Delta (G)$; if $\Delta (G)=|V(G)|-1$, then $\chi ^\prime (G)=ch^\prime (G)=\Delta (G)$ if and only if $G\not= K_3$.

Ключевые слова: chromatic number, chromatically equivalent, chromatically unique graph, chromatic index, list-chromatic index.

УДК: 519.17

Язык публикации: английский

DOI: 10.17223/20710410/50/7



Реферативные базы данных:


© МИАН, 2024