×

Adjacent vertex distinguishing indices of planar graphs without 3-cycles. (English) Zbl 1305.05053

Summary: Given a proper edge \(k\)-coloring \(\phi\) and a vertex \(v \in V(G)\), let \(C_\phi(v)\) denote the set of colors used on edges incident to \(v\) with respect to \(\phi\). The adjacent vertex distinguishing index of \(G\), denoted by \(\chi_a^\prime(G)\), is the least value of \(k\) such that \(G\) has a proper edge \(k\)-coloring which satisfies \(C_\phi(u) \neq C_\phi(v)\) for any pair of adjacent vertices \(u\) and \(v\). In this paper, we show that if \(G\) is a connected planar graph with maximum degree \(\Delta \geq 12\) and without 3-cycles, then \(\Delta \leq \chi_a^\prime(G) \leq \Delta + 1\), and \(\chi_a^\prime(G) = \Delta + 1\) if and only if \(G\) contains two adjacent vertices of maximum degree. This extends a result by K. Edwards et al. [Graphs Comb. 22, No. 3, 341–350 (2006; Zbl 1107.05032)], which says that if \(G\) is a connected bipartite planar graph with \(\Delta \geq 12\) then \(\chi_a^\prime(G) \leq \Delta + 1\).

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C07 Vertex degrees
05C38 Paths and cycles

Citations:

Zbl 1107.05032
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balister, P. N.; Győri, E.; Lehel, J.; Schelp, R. H., Adjacent vertex distinguishing edge-colorings, SIAM J. Discrete Math., 21, 237-250 (2007) · Zbl 1189.05056
[2] Bu, Y.; Lih, K.-W.; Wang, W., Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six, Discuss. Math. Graph Theory, 31, 429-439 (2011) · Zbl 1229.05100
[3] Edwards, K.; Hornáˇk, M.; Woźniak, M., On the neighbourdistinguishing index of a graph, Graphs Combin., 22, 341-350 (2006) · Zbl 1107.05032
[4] 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
[5] Hocquard, H.; Montassier, M., Adjacent vertex-distinguishing edge coloring of graphs with maximum degree at least five, Electron. Notes Discrete Math., 38, 457-462 (2011) · Zbl 1274.05159
[6] Hocquard, H.; Montassier, M., Adjacent vertex-distinguishing edge coloring of graphs with maximum degree \(\Delta \), J. Comb. Optim., 26, 152-160 (2013) · Zbl 1276.90079
[7] Horñák, M.; Huang, D.; Wang, W., On neighbor-distinguishing index of planar graphs, J. Graph Theory, 76, 262-278 (2014) · Zbl 1296.05072
[8] Wang, W.; Wang, Y., Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree, J. Comb. Optim., 19, 471-485 (2010) · Zbl 1221.05166
[9] Wang, W.; Wang, Y., Adjacent vertex distinguishing edge colorings of \(K_4\)-minor free graphs, Appl. Math. Lett., 24, 2034-2037 (2011) · Zbl 1234.05105
[10] Yan, C.; Huang, D.; Chen, D.; Wang, W., Adjacent vertex distinguishing edge colorings of planar graphs with girth at least five, J. Comb. Optim., 28, 893-909 (2014) · Zbl 1337.90077
[11] Yan, C.; Huang, D.; Wang, W., Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least four, J. Math. Study, 45, 331-341 (2012) · Zbl 1289.05108
[12] 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.