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

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

Эта публикация цитируется в 1 статье

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

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