Name
Abstract | ||
|---|---|---|
For a planar graph $G$, let $\Delta(G)$, $g(G)$, and $\lambda(G;p,q)$ denote, respectively, its maximum degree, girth, and $L(p,q)$-labeling number. We prove that (1) $\lambda(G;p,q)\le (2q-1)\Delta(G)+4p+4q-4$ if $g(G)\ge 7$; (2) $\lambda(G;p,q)\le (2q-1)\Delta(G)+6p+12q-9$ if $g(G)\ge 6$; (3) $\lambda(G;p,q)\le (2q-1)\Delta(G)+6p+24q-15$ if $g(G)\ge 5$. These bounds have consequences on conjectures by Wegner [Graphs with Given Diameter and a Coloring Problem, preprint, University of Dortmund, Dortmund, Germany, 1977] and Griggs and Yeh [SIAM J. Discrete Math., 5 (1992), pp. 586--595]. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1137/S0895480101390448 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
maximum degree,planar graphs,planar graph,coloring problem,siam j. discrete math | Discrete mathematics,Graph,Combinatorics,Degree (graph theory),Mathematics,Planar graph,Lambda,Coloring problem | Journal |
Volume | Issue | ISSN |
17 | 2 | 0895-4801 |
Citations | PageRank | References |
46 | 3.43 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Weifan Wang | 1 | 868 | 89.92 |
| Ko-wei Lih | 2 | 529 | 58.80 |