|
East Asian Journal on Applied Mathematics, 2 (2012), pp. 83-93. |
|
L-Factors and Adjacent Vertex-Distinguishing Edge-Weighting Yinghua Duan 1, Hongliang Lu 2*, Qinglin Yu 3 1 Department of Mathematics, Beijing National Day School, Beijing, PR China.2 School of Mathematics and Statistics, Xi'an Jiaotong University, Xi'an 710049, PR China. 2 Department of Mathematics and Statistics, Thompson Rivers University, Kamloops, BC, Canada. Received 8 April 2011; Accepted (in revised version) 29 December 2011 Available online 27 April 2012 doi:10.4208/eajam.080411.291211a Abstract An edge-weighting problem of a graph $G$ is an assignment of an integer weight to each edge $e$. Based on an edge-weighting problem, several types of vertex-coloring problems are put forward. A simple observation illuminates that the edge-weighting problem has a close relationship with special factors of the graphs. In this paper, we generalise several earlier results on the existence of factors with pre-specified degrees and hence investigate the edge-weighting problem --- and in particular, we prove that every $4$-colorable graph admits a vertex-coloring $4$-edge-weighting. AMS subject classifications: 05C70, 05C15Key words: Edge-weighting, vertex-coloring, L-factor. *Corresponding author. Email: luhongliang215@sina.com (H. Lu), yinghua115@mail.nankai.edu.cn (Y. Duan), yu@tru.ca (Q. Yu) |