Geodesic
On the $\rho$-subdivision number of graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 979-997

Voir la notice de l'article provenant de la source Library of Science

For an arbitrary invariant ρ(G) of a graph G the ρ-subdivision number sd_ρ(G) is the minimum number of edges of G whose subdivision results in a graph H with ρ(H) ρ(G). Set sd_ρ(G) = |E(G)| if such an edge set does not exist. In the first part of this paper we give some general results for the ρ-subdivision number. In the second part we study this parameter for the chromatic number, for the chromatic index, and for the total chromatic number. We show among others that there is a strong relationship to the ρ-edge stability number for these three invariants. In the last part we consider a modification, namely the ρ-multiple subdivision number where we allow multiple subdivisions of the same edge.
Keywords: subdivision number, edge stability number, edge subdivision, chromatic number, chromatic index, total chromatic number 
@article{DMGT_2023_43_4_a6,
     author = {Kemnitz, Arnfried and Marangio, Massimiliano},
     title = {On the $\rho$-subdivision number of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {979--997},
     publisher = {mathdoc},
     volume = {43},
     number = {4},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a6/}
}
TY  - JOUR
AU  - Kemnitz, Arnfried
AU  - Marangio, Massimiliano
TI  - On the $\rho$-subdivision number of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 979
EP  - 997
VL  - 43
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a6/
LA  - en
ID  - DMGT_2023_43_4_a6
ER  - 
%0 Journal Article
%A Kemnitz, Arnfried
%A Marangio, Massimiliano
%T On the $\rho$-subdivision number of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 979-997
%V 43
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a6/
%G en
%F DMGT_2023_43_4_a6
Kemnitz, Arnfried; Marangio, Massimiliano. On the $\rho$-subdivision number of graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 979-997. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a6/