Graphs with multiplicative vertex-coloring 2-edge-weightings

Joanna Skowronek-Kaziów ()
Additional contact information
Joanna Skowronek-Kaziów: University of Zielona Góra

Journal of Combinatorial Optimization, 2017, vol. 33, issue 1, No 24, 333-338

Abstract: Abstract A k-weighting w of a graph is an assignment of an integer weight $$w(e)\in \{1,...k\}$$ w ( e ) ∈ { 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).$$ c ( v ) = ∏ v ∈ 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)$$ c ( u ) ≠ c ( v ) for any edge $$uv\in E(G).$$ u v ∈ E ( G ) . This paper studies the parameter $$\mu (G),$$ μ ( 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$$ r ≥ 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$$ μ ( G ) ≤ 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}$$ C 6 and the path $$P_{6}$$ 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$$ μ ( 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)$$ G = ( A , B , E ) with even $$\left| A\right| $$ A or $$\left| B\right| $$ B .

Keywords: Edge weighting; Vertex coloring; 1-2-3 Conjecture; 05C15; 05C85 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9966-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:33:y:2017:i:1:d:10.1007_s10878-015-9966-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9966-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().