Tight Bounds for the N₂-Chromatic Number of Graphs
DOI:
https://doi.org/10.22199/issn.0717-6279-6117Keywords:
Vertex coloring, $N_2$-vertex coloring, $N_2$-chromatic number, maximum degree, diameterAbstract
Let $G$ be a connected graph. A vertex coloring of $G$ is an $N_2$-vertex coloring if, for every vertex $v$, the number of different colors assigned to the vertices adjacent to $v$ is at most two. The $N_2$-chromatic number of $G$ is the maximum number of colors that can be used in an $N_2$-vertex coloring of $G$. In this paper, we establish tight bounds for the $N_2$-chromatic number of a graph in terms of its maximum degree and its diameter, and characterize those graphs that attain these bounds.
References
S. Akbari, N. Alipourfard, P. Jandaghi, and M. Mirtaheri, On $N_2$-vertex coloring of graphs, Discrete Math. Algorithms Appl. 10 (1) (2018), 1850007.
J. Akiyama and F. Harary, A graph and its complement with specified properties III: girth and circumference, Int. J. Math. Math. Sci. 2 (1979), 685--692.
F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, 1990.
K. Budajov'{a} and J. Czap, $M_2$-edge coloring and maximum matching of graphs, Int. J. Pure Appl. Math. 88 (2) (2013), 161--167.
J. Czap, $M_i$-edge colorings of graphs, Appl. Math. Sci. (Ruse) 5 (49) (2011), 2437--2442.
J. Czap, J. Ivanv{c}o, and P. v{S}ugerek, $M_2$-edge colorings of cacti and graph joins, Discuss. Math. Graph Theory 36 (1) (2016), 59--69.
B. Elspas, Topological constraints on interconnection-limited logic, 1964 Proc. of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design, IEEE S-164 (1964), 133--147.
M. Miller and J. v{S}ir'{a}v{n}, Moore graphs and beyond: a survey of the degree/diameter problem, Electron. J. Combin. 20 (2) (2013) #DS14v2.
S.G. Molodtsov, Largest graphs of diameter $2$ and maximum degree $6$, in Information Transfer and Combinatorics, R. Ahlswede et al. (Eds.), Springer LNCS 4123 (2006), 853--857.
Published
How to Cite
Issue
Section
Copyright (c) 2024 Ian June Garces
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
