Contents Online

# Journal of Combinatorics

## Volume 2 (2011)

### Number 4

### Primality of trees

Pages: 481 – 500

DOI: http://dx.doi.org/10.4310/JOC.2011.v2.n4.a1

#### Authors

#### Abstract

A graph of order $n$ is $prime$ if one can bijectively label its vertices with integers $1,\dots,n$ so that any two adjacent vertices get coprime labels. We prove that all bipartite $d$-degenerate graphs with separators of size at most $n^{1-O_d(1/\ln\ln n)}$ are prime. It immediately follows that all large trees are prime, confirming an old conjecture of Entringer and Tout from around 1980. Also, our method allows us to determine the smallest size of a non-prime connected order-$n$ graph for all large $n$, proving a conjecture of Rao [R. C. Bose Centenary Symposium on Discrete Math. and Applications, Kolkata, 2002] in this range.

#### Keywords

coprime graph, prime labeling, Entringer–Tout conjecture

#### 2010 Mathematics Subject Classification

05C78