DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

J. Czap

Július Czap

Department of Applied Mathematics and Business Informatics
Faculty of Economics
Technical University of Kosice

email: julius.czap@tuke.sk

0000-0002-9933-5884

S. Jendrol'

Stanislav Jendrol'

Institute of Mathematics, P. J. Šafárik University in Košice, Jesenná 5, SK-041 54 Košice

email: stanislav.jendrol@upjs.sk

0000-0001-6869-2793

P. Šugerek

Peter Šugerek

Department of Applied Mathematics and Business Informatics, Faculty of Economics, Technical University of Kosice, Kosice

email: peter.sugerek@tuke.sk

0000-0002-5746-846X

Title:

On $\mathcal P$ vertex-connections of graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 45(2) (2025) 637-652

Received: 2023-11-20 , Revised: 2024-04-18 , Accepted: 2024-04-27 , Available online: 2024-06-13 , https://doi.org/10.7151/dmgt.2545

Abstract:

A vertex colored graph $G$ is $\mathcal P$ vertex-connected if every two vertices of $G$ are connected by a path having property $\mathcal P$. The problem is to find the minimum integer $k$ for which there exists a vertex $k$-coloring of $G$ that makes it $\mathcal P$ vertex-connected. In this note we introduce some modifications of this problem and determine upper bounds for the corresponding graph parameters. We deal with four properties, namely with property to be zig-zag, to be dynamic, to be nonrepetitive, and to be conflict-free.

Keywords:

edge coloring, vertex coloring, $\mathcal P$ connection, $\mathcal P$ vertex-connection

References:

  1. N. Alon, J. Grytczuk, M. Hałuszczak and O. Riordan, Nonrepetitive coloring of graphs, Random Structures Algorithms 21 (2002) 336–346.
    https://doi.org/10.1002/rsa.10057
  2. V. Borozan, S. Fujita, A. Gerek, C. Magnant, Y. Manoussakis, L. Montero and Zs. Tuza, Proper connection of graphs, Discrete Math. 312 (2012) 2550–2560.
    https://doi.org/10.1016/j.disc.2011.09.003
  3. Ch. Brause, S. Jendroľ and I. Schiermeyer, Odd connection and odd vertex connection of graphs, Discrete Math. 341 (2018) 3500–3512.
    https://doi.org/10.1016/j.disc.2018.09.002
  4. B. Brešar, J. Grytczuk, S. Klavžar, S. Niwczyk and I. Peterin, Nonrepetitive colorings of trees, Discrete Math. 307 (2007) 163–172.
    https://doi.org/10.1016/j.disc.2006.06.017
  5. Q. Cai, X. Li and D. Wu, Some extremal results on the colorful monochromatic vertex-connectivity of a graph, J. Comb. Optim. 35 (2018) 1300–1311.
    https://doi.org/10.1007/s10878-018-0258-x
  6. Y. Caro and R. Yuster, Colorful monochromatic connectivity, Discrete Math. 311 (2011) 1786–1792.
    https://doi.org/10.1016/j.disc.2011.04.020
  7. G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85–98.
    https://doi.org/10.21136/MB.2008.133947
  8. E. Chizmar, C. Magnant and P.S. Nowbandegani, Note on vertex and total proper connection numbers, AKCE Int. J. Graphs Comb. 13 (2016) 103–106.
    https://doi.org/10.1016/j.akcej.2016.06.003
  9. J. Czap, S. Jendroľ and J. Valiska, Conflict-free connections of graphs, Discuss. Math. Graph Theory 38 (2018) 911–920.
    https://doi.org/10.7151/dmgt.2036
  10. T.D. Doan, P.H. Ha and I. Schiermeyer, The conflict-free vertex-connection number and degree conditions of graphs, Graphs Combin. 38 (2022) 157.
    https://doi.org/10.1007/s00373-022-02567-y
  11. T.D. Doan and I. Schiermeyer, Conflict-free vertex connection number at most $3$ and size of graphs, Discuss. Math. Graph Theory 41 (2021) 617–632.
    https://doi.org/10.7151/dmgt.2211
  12. V. Dujmović, L. Esperet, G. Joret, B. Walczak and D.R. Wood, Planar graphs have bounded nonrepetitive chromatic number, Adv. Comb 5 (2020) 1–11.
    https://doi.org/10.19086/aic.12100
  13. V. Dujmović, G. Joret, J. Kozik and D.R. Wood, Nonrepetitive colouring via entropy compression, Combinatorica 36 (2016) 661–686.
    https://doi.org/10.1007/s00493-015-3070-6
  14. M. Ji, X. Li and I. Schiermeyer, Upper bounds and extreme results for conflict-free vertex connection number, J. Phys. Conf. Ser. 1995 (2021) 012060.
    https://doi.org/10.1088/1742-6596/1995/1/012060
  15. M. Krivelevich and R. Yuster, The rainbow connection of a graph is $($at most$)$ reciprocal to its minimum degree, J. Graph Theory 63 (2010) 185–191.
    https://doi.org/10.1002/jgt.20418
  16. X. Li and C. Magnant, Properly colored notions of connectivity –- A dynamic survey, Theory Appl. Graphs 0(1) (2015) 2.
    https://doi.org/10.20429/tag.2015.000102
  17. X. Li and Y. Sun, An updated survey on rainbow connections of graphs –- A dynamic survey, Theory Appl. Graphs 0(1) (2017) 3.
    https://doi.org/10.20429/tag.2017.000103
  18. X. Li, Y. Zhang, X. Zhu, Y. Mao, H. Zhao and S. Jendroľ, Conflict-free vertex-connections of graphs, Discuss. Math. Graph Theory 40 (2020) 51–65.
    https://doi.org/10.7151/dmgt.2116
  19. X. Li and D. Wu, A survey on monochromatic connections of graphs, Theory Appl. Graphs 0(1) (2018) 4.
    https://doi.org/10.20429/tag.2017.000104
  20. Z. Li and B. Wu, Maximum value of conflict-free vertex-connection number of graphs, Discrete Math. Algorithms Appl. 10 (2018) 1850059.
    https://doi.org/10.1142/S1793830918500593
  21. A. Thue, \$quot;Uber unendliche Zeichenreichen, Norske Vid. Selsk. Skr. I Mat. Nat. Kl. Christiana 7 (1906) 1–22, in German.
  22. D.R. Wood, Nonrepetitive graph colouring, Electron. J. Combin. Dynamic Surveys (2021) #DS24.
    https://doi.org/10.37236/9777
Close