Geodesic
Labeling planar graphs with a condition at distance two
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005) Cet article a éte moissonné depuis la source Episciences

Voir la notice de l'article

An $L(2,1)$-labeling of a graph is a mapping $c:V(G) \to \{0,\ldots,K\}$ such that the labels assigned to neighboring vertices differ by at least $2$ and the labels of vertices at distance two are different. Griggs and Yeh [SIAM J. Discrete Math. 5 (1992), 586―595] conjectured that every graph $G$ with maximum degree $\Delta$ has an $L(2,1)$-labeling with $K \leq \Delta^2$. We verify the conjecture for planar graphs with maximum degree $\Delta \neq 3$. 
@article{DMTCS_2005_special_250_a26,
     author = {Bella, Peter and Kr\'al, Daniel and Mohar, Bojan and Quittnerov\'a, Katarina},
     title = {Labeling planar graphs with a condition at distance two},
     journal = {Discrete mathematics & theoretical computer science},
     year = {2005},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     doi = {10.46298/dmtcs.3417},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3417/}
}
TY  - JOUR
AU  - Bella, Peter
AU  - Král, Daniel
AU  - Mohar, Bojan
AU  - Quittnerová, Katarina
TI  - Labeling planar graphs with a condition at distance two
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3417/
DO  - 10.46298/dmtcs.3417
LA  - en
ID  - DMTCS_2005_special_250_a26
ER  - 
%0 Journal Article
%A Bella, Peter
%A Král, Daniel
%A Mohar, Bojan
%A Quittnerová, Katarina
%T Labeling planar graphs with a condition at distance two
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3417/
%R 10.46298/dmtcs.3417
%G en
%F DMTCS_2005_special_250_a26
Bella, Peter; Král, Daniel; Mohar, Bojan; Quittnerová, Katarina. Labeling planar graphs with a condition at distance two. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi: 10.46298/dmtcs.3417

Cité par Sources :