No Access

On $N_{2}$ $N_{2}$ -vertex coloring of graphs

S. Akbari

Department of Mathematical Sciences, Sharif University of Technology, Azadi Avenue, Tehran 11365, Iran

E-mail Address: s_akbari@sharif.edu

Search for more papers by this author

N. Alipourfard

http://orcid.org/0000-0001-9971-2179

Information Sciences Institute, 4676 Admiralty Way, Marina Del Rey 90292, California, USA

E-mail Address: nalipour@usc.edu

Search for more papers by this author

P. Jandaghi

Information Sciences Institute, 4676 Admiralty Way, Marina Del Rey 90292, California, USA

E-mail Address: jandaghi@usc.edu

Search for more papers by this author

, and

M. Mirtaheri

Information Sciences Institute, 4676 Admiralty Way, Marina Del Rey 90292, California, USA

E-mail Address: mehrnoom@usc.edu

Search for more papers by this author

https://doi.org/10.1142/S1793830918500076Cited by:1 (Source: Crossref)

Abstract

Let $G$ be a graph. A vertex coloring $ψ$ of $G$ is called $N_{2}$ -vertex coloring if $| ψ (v) | \leq 2$ for every vertex $v$ of $G$ , where $ψ (v)$ is the set of colors of vertices adjacent to $v$ . Let $t_{2} (G)$ be the maximum number of colors used in an $N_{2}$ -vertex coloring of $G$ . We provide some lower and upper bounds for $t_{2} (G)$ in terms of girth, diameter or size of $G$ . Also, for every tree $T$ , we obtain $t_{2} (T)$ .

Keywords:

AMSC: 05C15, 05C85

References

1. K. Budajova and J. Czap, $M_{2}$ -edge coloring and maximum matching of graphs, Int. J. Pure Appl. Math. 88(2) (2013) 161–167. Google Scholar
2. J. Czap, $M_{i}$ -edge colorings of graphs, Appl. Math. Sci. 5(49) (2011) 2437–2442. Google Scholar
3. J. Czap, J. Ivanco and P. Sugerek, M2-edge colorings of cacti and graph joins, Discuss. Math. Graph Theory 36 (2016) 59–69. Crossref, Google Scholar