Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Digraphs are 2-weight choosable. | Digraphs are 2-weight choosable Mahdad Khatirinejad t Reza Naserasr - Mike Newman t Ben Seamone Brett Stevens Submitted Feb 21 2010 Accepted Jan 12 2011 Published Jan 19 2011 Mathematics Subject Classifications 05C22 05C15 Abstract An edge-weighting vertex colouring of a graph is an edge-weight assignment such that the accumulated weights at the vertices yield a proper vertex colouring. If such an assignment from a set S exists we say the graph is S-weight colourable. We consider the S-weight colourability of digraphs by defining the accumulated weight at a vertex to be the sum of the inbound weights minus the sum of the outbound weights. Bartnicki et al. showed that every digraph is S-weight colourable for any set S of size 2 and asked whether one could show the same result using an algebraic approach. Using the Combinatorial Nullstellensatz and a classical theorem of Schur we provide such a solution. Let G be a simple graph with no isolated edge and S be a set of real numbers. An S-edge-weighting of G is an assignment w E G S. The weighted degree of a vertex is the sum of weights of the edges incident with it. If the weighted degrees of adjacent vertices are different we say that w is an S-weight colouring and we say that G is S-weight colourable. Karonski et al. KLT04 asked whether every graph is 1 2 3 -weight colourable they showed this is true for 3-colourable graphs. Kalkowski et al. KKP09 showed that general graphs are 1 2 3 4 5 -weight colourable. We generalize S-weight colourings to directed graphs by defining the weighted degree of a vertex of D to be the sum of the inbound weights minus the sum of the outbound weights of that vertex. We allow our digraphs to contain multiple parallel arcs in either direction but no loops. These problems have natural list-colouring variants. Suppose that each e G E G of a directed graph G is assigned a set of real numbers Le. Let L UeeE G Le. The Department of Communications and Networking Aalto University 13000 .
