Geodesic
Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Twenty-fifth International Symposium on Graph Drawing and Network Visualization, GD 2017 , Tome 22 (2018) no. 3, pp. 483-499.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We show that triangle-free penny graphs have degeneracy at most two, and that both triangle-free penny graphs and squaregraphs have at most $\min\bigl(2n-\Omega(\sqrt n),2n-D-2\bigr)$ edges, where $n$ is the number of vertices and $D$ is the diameter of the graph.
DOI : 10.7155/jgaa.00463
Keywords: squaregraph, penny graph, triangle-free graph, unit disk contact graph, minimum-distance graph, graph degeneracy, list coloring 
@article{JGAA_2018_22_3_a4,
     author = {David Eppstein},
     title = {Edge {Bounds} and {Degeneracy} of {Triangle-Free} {Penny} {Graphs} and {Squaregraphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {483--499},
     publisher = {mathdoc},
     volume = {22},
     number = {3},
     year = {2018},
     doi = {10.7155/jgaa.00463},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00463/}
}
TY  - JOUR
AU  - David Eppstein
TI  - Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2018
SP  - 483
EP  - 499
VL  - 22
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00463/
DO  - 10.7155/jgaa.00463
LA  - en
ID  - JGAA_2018_22_3_a4
ER  - 
%0 Journal Article
%A David Eppstein
%T Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs
%J Journal of Graph Algorithms and Applications
%D 2018
%P 483-499
%V 22
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00463/
%R 10.7155/jgaa.00463
%G en
%F JGAA_2018_22_3_a4
David Eppstein. Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Twenty-fifth International Symposium on Graph Drawing and Network Visualization, GD 2017
					, Tome 22 (2018) no. 3, pp. 483-499. doi : 10.7155/jgaa.00463. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00463/

Cité par Sources :