|
|||||
|
|
Vertex Coloring of Graphs by Total 2-Weightings |
|
| Authors: | Jonathan Hulgan Jenő Lehel Kenta Ozeki Kiyoshi Yoshimoto |
| Affiliation: | 1.Department of Mathematics and Computer Science,Oxford College of Emory University,Oxford,USA;2.University of Louisville,Louisville,USA;3.Alfréd Rényi Institute of Mathematics,Hungarian Academy of Sciences,Budapest,Hungary;4.National Institute of Informatics,2-1-2 Hitotsubashi,Tokyo,Japan;5.JST, ERATO, Kawarabayashi Large Graph Project,Tokyo,Japan;6.Department of Mathematics, College of Science and Technology,Nihon University,Tokyo,Japan |
| Abstract: | An assignment of weights to the edges and the vertices of a graph is a vertex-coloring total weighting if adjacent vertices have different total weight sums. Of interest in this paper are vertex-coloring total weightings with weight set of cardinality two, a problem motivated by the conjecture that every graph has such a weighting using the weights 1 and 2. Here we prove the existence of such weightings for certain families of graphs using any two different real weights. A related problem where all vertices have unique weight sums is also discussed. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |