×

Further results on 2-distance coloring of graphs. (English) Zbl 1507.05039

Summary: Given a graph \(G=\big( V(G),E(G)\big)\), a mapping from \(V(G)\) to \(\{1,\ldots,|V(G)|\}\) (the numbers \(1,\ldots,|V(G)|\) are usually called colors) is said to be a 2-distance coloring of \(G\) if any two vertices at distance at most two from each other receive different colors. Such a mapping with the minimum number of colors is said to be an optimal 2-distance coloring of \(G\). The 2-distance chromatic number \(\chi_2 (G)\) of a graph \(G\) is the number of colors assigned by an optimal 2-distance coloring to the vertices of \(G\). In this paper, we continue the study of this classic topic in graph theory. The main focus of this work is given to this parameter in some graph products, where we investigate this type of coloring in the strong, direct and rooted products. In particular, in the case of rooted products (in its most general case) we give an exact formula for the 2-distance chromatic number. This improves the results in a previous paper bounding this parameter from below and above in a special case. We next give bounds on this parameter for general graphs as well as the exact values for it in some well-known families of graphs.

MSC:

05C15 Coloring of graphs and hypergraphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C76 Graph operations (line graphs, products, etc.)
Full Text: DOI

References:

[1] Aouchiche, M.; Hansen, P., A survey of Nordhaus-Gaddum type relations, Discret Appl Math, 161, 466-546 (2013) · Zbl 1259.05083 · doi:10.1016/j.dam.2011.12.018
[2] Cockayne, EJ; Hedetniemi, ST, Towards a theory of domination in graphs, Networks, 7, 247-261 (1977) · Zbl 0384.05051 · doi:10.1002/net.3230070305
[3] Ghazi, G.; Rahbarnia, F.; Tavakoli, M., 2-Distance chromatic number of some graph products, Discret Math Algorithms Appl, 12, 2050021 (2020) · Zbl 1456.05062 · doi:10.1142/S1793830920500214
[4] Godsil, CD; McKay, BD, A new graph product and its spectrum, Bull Aust Math Soc, 18, 21-28 (1978) · Zbl 0376.05049 · doi:10.1017/S0004972700007760
[5] Hammack, R.; Imrich, W.; Klavžar, S., Handbook of product graphs (2011), Boca Raton, FL: CRC Press, Boca Raton, FL · Zbl 1283.05001 · doi:10.1201/b10959
[6] Haynes TW, Hedetniemi ST, Henning MA (eds) (2020) Topics in domination in graphs. Springer International Publishing, Switzerland · Zbl 1526.05002
[7] Haynes, TW; Hedetniemi, ST; Slater, PJ, Fundamentals of domination in graphs (1998), New York: Marcel Dekker, New York · Zbl 0890.05002
[8] Henning, MA; Slater, PJ, Open packing in graphs, J Comb Math Comb Comput, 28, 5-18 (1999) · Zbl 0922.05040
[9] Huang, KC; Lih, KW, Nordhaus-Gaddum type relations of three graph coloring parameters, Discret Appl Math, 162, 404-408 (2014) · Zbl 1300.05099 · doi:10.1016/j.dam.2013.08.043
[10] Kramer, F.; Kramer, H., Ein Färbungsproblem der knotenpunkte eines graphen bezüglich der distanz \(p\), Rev Roum Math Pures Appl, 14, 1031-1038 (1969) · Zbl 0194.25201
[11] Kramer, F.; Kramer, H., Un probleme de coloration des sommets d’un graphe, CR Acad Sci Paris A, 268, 46-48 (1969) · Zbl 0165.57302
[12] Ma, B.; Chen, X.; Liu, J., \(2\)-Distance coloring of strong product of graphs, J Shandong Univ Nat Sci, 45, 66-70 (2010) · Zbl 1224.05180
[13] McCormick, ST, Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem, Math Programm, 26, 153-171 (1983) · Zbl 0507.65027 · doi:10.1007/BF02592052
[14] Niranjan, PK; Kola, SR, The \(k\)-distance chromatic number of trees and cycles, AKCE Int. J. Graphs Comb., 16, 230-235 (2019) · Zbl 1432.05043 · doi:10.1016/j.akcej.2017.11.007
[15] Schwenk AJ (1974) Computing the characteristic polynomial of a graph. In: Bari R and Harary F (eds) Graphs and combinatorics. Springer, Berlin, pp 153-172 · Zbl 0308.05121
[16] West DB (2001) Introduction to graph theory, 2nd edn. Prentice Hall, USA
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.