Informace o publikaci
Facial colorings using Hall's Theorem
| Autoři | |
|---|---|
| Rok publikování | 2010 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | European Journal of Combinatorics |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.ejc.2009.10.003 |
| Popis | A vertex coloring of a plane graph is l-facial if every two distinct vertices joined by a facial walk of length at most l receive distinct colors. It has been conjectured that every plane graph has l-facial coloring with at most 3l+1 colors We improve the currently best known bound and show that every plane graph has ail l-facial coloring with at most [7l/2] + 6 colors. Our proof uses the standard discharging technique, however, in the reduction part we have successfully applied Hall's Theorem. which seems to be quite all unusual approach in this area (C) 2009 Elsevier Ltd. All rights reserved |