Graphs with multiplicative vertex-coloring 2-edge-weightings

详细信息    查看全文

• 作者：Joanna Skowronek-Kaziów
• 关键词：Edge weighting ; Vertex coloring ; 1 ; 2 ; 3 Conjecture
• 刊名：Journal of Combinatorial Optimization
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：33
• 期：1
• 页码：333-338
• 全文大小：360KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Convex and Discrete Geometry; Mathematical Modeling and Industrial Mathematics; Theory of Computation; Optimization; Operation Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2886
• 卷排序：33

文摘

A k-weighting w of a graph is an assignment of an integer weight \(w(e)\in \{1,...k\}\) to each edge e. Such an edge weighting induces a vertex coloring c defined by \(c(v)=\mathop {\displaystyle {\prod }}\limits _{v\in e}w(e).\) A k-weighting of a graph G is multiplicative vertex-coloring if the induced coloring c is proper, i.e., \(c(u)\ne c(v)\) for any edge \(uv\in E(G).\) This paper studies the parameter \(\mu (G),\) which is the minimum k for which G has a multiplicative vertex-coloring k-weighting. Chang, Lu, Wu, Yu investigated graphs with additive vertex-coloring 2-weightings (they considered sums instead of products of incident edge weights). In particular, they proved that 3-connected bipartite graphs, bipartite graphs with the minimum degree 1, and r-regular bipartite graphs with \(r\ge 3\) permit an additive vertex-coloring 2-weighting. In this paper, the multiplicative version of the problem is considered. It was shown in Skowronek-Kaziów (Inf Process Lett 112:191–194, 2012) that \(\mu (G)\le 4\) for every graph G. It was also proved that every 3-colorable graph admits a multiplicative vertex-coloring 3 -weighting. A natural problem to consider is whether every 2-colorable graph (i.e., a bipartite graph) has a multiplicative vertex-coloring 2-weighting. But the answer is no, since the cycle \(C_{6}\) and the path \(P_{6}\) do not admit a multiplicative vertex-coloring 2-weighting. The paper presents several classes of 2-colorable graphs for which \(\mu (G)=2\), including trees with at least two adjacent leaf edges, bipartite graphs with the minimum degree 3 and bipartite graphs \(G=(A,B,E)\) with even \(\left| A\right| \) or \(\left| B\right| \).