Adjacent vertex distinguishing edge-colorings and total-colorings of the lexicographic product of graphs. (English) Zbl 1310.05101
Summary: Let \(G\) be a simple graph with vertex set \(V(G)\) and edge set \(E(G)\). An edge-coloring \(f\) of \(G\) is called an adjacent vertex distinguishing edge-coloring of \(G\) if \(C_f(u) \neq C_f(v)\) for any \(u v \in E(G)\), where \(C_f(u)\) denotes the set of colors of edges incident with \(u\). A total-coloring \(g\) of \(G\) is called an adjacent vertex distinguishing total-coloring of \(G\) if \(S_g(u) \neq S_g(v)\) for any \(u v \in E(G)\), where \(S_g(u)\) denotes the set of colors of edges incident with \(u\) together with the color assigned to \(u\). The minimum number of colors required for an adjacent vertex distinguishing edge-coloring (resp. an adjacent vertex distinguishing total-coloring) of \(G\) is denoted by \(\chi_a^\prime(G)\) (resp. \(\chi_{a t}(G)\)). The lexicographic product of simple graphs \(G\) and \(H\) is simple graph \(G [H]\) with vertex set \(V(G) \times V(H)\), in which \((u, v)\) is adjacent to \((u', v^\prime)\) if and only if either \(u u^\prime\in E(G)\) or \(u = u^\prime\) and \(v v^\prime \in E(H)\).
In this paper, we consider these parameters for the lexicographic product \(G [H]\) of two graphs \(G\) and \(H\). We give the exact values of \(\chi_a^\prime(G [H])\) if (1) \(G\) is a complete graph of order \(n \geq 3\) and \(H\) is a graph of order \(2 m \geq 4\) with \(\chi_a^\prime(H) = \Delta(H)\); (2) \(G\) is a tree of order \(n \geq 3\) and \(H\) is a graph of order \(m \geq 3\) with \(\chi_a^\prime(H) = \Delta(H)\).
We also obtain the exact values of \(\chi_{a t}(G [H])\) if (1) \(G\) is a complete graph of order \(n \geq 2\) and \(H\) is an empty graph of order \(m \geq 2\), where \(n m\) is even; (2) \(G\) is a complete graph of order \(n \geq 2\) and \(H\) is a bipartite graph of order \(m \geq 4\) with bipartition \((X, Y)\), where \(| X |\) and \(| Y |\) are even; (3) \(G\) is a cycle of order \(n \geq 3\) and \(H\) is an empty graph of order \(m \geq 2\), where \(n m\) is even; (4) \(G\) is a tree of order \(n \geq 3\) and \(H\) is an empty graph of order \(m \geq 2\).
In this paper, we consider these parameters for the lexicographic product \(G [H]\) of two graphs \(G\) and \(H\). We give the exact values of \(\chi_a^\prime(G [H])\) if (1) \(G\) is a complete graph of order \(n \geq 3\) and \(H\) is a graph of order \(2 m \geq 4\) with \(\chi_a^\prime(H) = \Delta(H)\); (2) \(G\) is a tree of order \(n \geq 3\) and \(H\) is a graph of order \(m \geq 3\) with \(\chi_a^\prime(H) = \Delta(H)\).
We also obtain the exact values of \(\chi_{a t}(G [H])\) if (1) \(G\) is a complete graph of order \(n \geq 2\) and \(H\) is an empty graph of order \(m \geq 2\), where \(n m\) is even; (2) \(G\) is a complete graph of order \(n \geq 2\) and \(H\) is a bipartite graph of order \(m \geq 4\) with bipartition \((X, Y)\), where \(| X |\) and \(| Y |\) are even; (3) \(G\) is a cycle of order \(n \geq 3\) and \(H\) is an empty graph of order \(m \geq 2\), where \(n m\) is even; (4) \(G\) is a tree of order \(n \geq 3\) and \(H\) is an empty graph of order \(m \geq 2\).
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
Keywords:
edge-coloring; total-coloring; adjacent vertex distinguishing edge-coloring; adjacent vertex distinguishing total-coloring; lexicographic productReferences:
| [1] | Akbari, S.; Bidkhori, H.; Nosrati, N., \(r\)-Strong edge colorings of graphs, Discrete Math., 306, 3005-3010 (2006) · Zbl 1112.05035 |
| [2] | Balister, P. N.; Győri, E.; Lehel, J.; Schelp, R. H., Adjacent vertex distinguishing edge-colorings, SIAM J. Discrete Math., 21, 1, 237-250 (2007) · Zbl 1189.05056 |
| [3] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), American Elsevier: American Elsevier New York · Zbl 1134.05001 |
| [4] | Chen, M.; Guo, X., Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes, Inform. Process. Lett., 109, 599-602 (2009) · Zbl 1197.05045 |
| [5] | Edwards, K.; Horňák, M.; Woźniak, M., On the neighbor-distinguishing index of a graph, Graphs Combin., 22, 341-350 (2006) · Zbl 1107.05032 |
| [6] | Hatami, H., \( \Delta + 300\) is a bound on the adjacent vertex distinguishing edge chromatic number, J. Combin. Theory Ser. B, 95, 246-256 (2005) · Zbl 1075.05034 |
| [7] | Tian, S.; Chen, P., On adjacent vertex-distinguishing total coloring of two classes of product graphs, J. Math. Res. Exposition, 27, 4, 733-737 (2007) · Zbl 1150.05345 |
| [8] | Tian, S.; Chen, P., On the adjacent vertex-distinguishing total coloring of \(K(r, 2 m)\), J. Zhejiang Normal Univ. Natur. Sci., 31, 1, 23-25 (2008) · Zbl 1174.05375 |
| [9] | Tian, S.; Li, J.; Zhang, Z., The adjacent strong edge chromatic number of \(K(r, 2)\), Math. Econ., 22, 1, 105-107 (2005) |
| [10] | Wang, H., On the adjacent vertex-distinguishing total chromatic numbers of the graphs with \(\Delta(G) = 3\), J. Comb. Optim., 14, 87-109 (2007) · Zbl 1125.05043 |
| [11] | Yap, H. P., Total Coloring of Graph (1996), Springer Verlag: Springer Verlag New York · Zbl 0839.05001 |
| [12] | Zhang, Z.; Chen, X.; Li, J.; Yao, B.; Lu, X.; Wang, J., On adjacent-vertex-distinguishing total coloring of graphs, Sci. China Ser. A, 48, 3, 289-299 (2005) · Zbl 1080.05036 |
| [13] | Zhang, Z.; Liu, L.; Wang, J., Adjacent strong edge coloring of graphs, Appl. Math. Lett., 15, 623-626 (2002) · Zbl 1008.05050 |
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.
