Geodesic
The chromaticity of the join of tree and null graph
Prikladnaâ diskretnaâ matematika, no. 4 (2020), pp. 93-101.

Voir la notice de l'article provenant de la source Math-Net.Ru

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$.
Keywords: chromatic number, chromatically equivalent, chromatically unique graph, chromatic index, list-chromatic index. 
@article{PDM_2020_4_a6,
     author = {L. X. Hung},
     title = {The chromaticity of the join of tree and null graph},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {93--101},
     publisher = {mathdoc},
     number = {4},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PDM_2020_4_a6/}
}
TY  - JOUR
AU  - L. X. Hung
TI  - The chromaticity of the join of tree and null graph
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2020
SP  - 93
EP  - 101
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2020_4_a6/
LA  - en
ID  - PDM_2020_4_a6
ER  - 
%0 Journal Article
%A L. X. Hung
%T The chromaticity of the join of tree and null graph
%J Prikladnaâ diskretnaâ matematika
%D 2020
%P 93-101
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2020_4_a6/
%G en
%F PDM_2020_4_a6
L. X. Hung. The chromaticity of the join of tree and null graph. Prikladnaâ diskretnaâ matematika, no. 4 (2020), pp. 93-101. http://geodesic.mathdoc.fr/item/PDM_2020_4_a6/

[1] M. Behzad, G. Chartrand, Introduction to the Theory of Graphs, Allyn and Bacon, Boston, 1971

[2] G. D. Birkhoff, “A determinant formula for the number of ways of coloring a map”, Ann. Math., 14:2 (1912), 42–46

[3] K. M. Koh, K. L. Teo, “The search for chromatically unique graphs”, Graphs Combin., 1990, no. 6, 259–285

[4] C. Y. Chao, E. G. Whitehead Jr., “On chromatic equivalence of graphs”, Lecture Notes Math., 642, 1978, 121–131

[5] K. M. Koh, K. L. Teo, “The search for chromatically unique graphs II”, Discrete Math., 172 (1997), 59–78

[6] N. D. Tan, L. X. Hung, “On colorings of split graphs”, Acta Mathematica Vietnammica, 31:3 (2006), 195–204

[7] V. G. Vizing, “On an estimate of the chromatic class of a p-graph”, Discret. Analiz, 1964, no. 3, 23–30 (in Russian)

[8] V. G. Vizing, “Coloring the vertices of a graph in prescribed colors”, Diskret. Analiz, 1976, no. 29, 3–10 (in Russian)

[9] P. Erdös, A. L. Rubin, H. Taylor, “Choosability in graphs”, Proc. West Coast Conf. Combin., Graph Theory, and Computing (Arcata, CA, September), Congressus Numerantium, XXVI, 1979, 125–157

[10] L. X. Hung, “List-chromatic number and chromatically unique of the graph $K_2^r+O_k$”, Selecciones Matemáticas, Universidad Nacional de Trujillo, 06:01 (2019), 26–30

[11] L. X. Hung, “Colorings of the graph $K^m_2 + K_n$”, J. Siberian Federal University. Mathematics Physics, 13:3 (2020), 297–305

[12] R. C. Read, “An introduction to chromatic polynomials”, J. Combin. Theory, 1968, no. 4, 52–71

[13] F. Brenti, “Expansions of chromatic polynomial and log-concavity”, Trans. Amer. Math. Soc., 332 (1992), 729–756

[14] R. Y. Liu, “A new method to find the chromatic polynomial of a graph and its applications”, Kexue Tongbao, 32 (1987), 1508–1509

[15] R. Diestel, Graph Theory, Springer Verlag, N.Y., 2000

[16] M. Plantholt, “The chromatic index of graphs with a spanning star”, J. Graph Theory, 1981, no. 5, 5–13