Total weight choosability of Mycielski graphs

Yunfang Tang () and Xuding Zhu ()
Additional contact information
Yunfang Tang: Tongji University
Xuding Zhu: Zhejiang Normal University

Journal of Combinatorial Optimization, 2017, vol. 33, issue 1, No 12, 165-182

Abstract: Abstract A total weighting of a graph G is a mapping $$\phi $$ ϕ that assigns a weight to each vertex and each edge of G. The vertex-sum of $$v \in V(G)$$ v ∈ V ( G ) with respect to $$\phi $$ ϕ is $$S_{\phi }(v)=\sum _{e\in E(v)}\phi (e)+\phi (v)$$ S ϕ ( v ) = ∑ e ∈ E ( v ) ϕ ( e ) + ϕ ( v ) . A total weighting is proper if adjacent vertices have distinct vertex-sums. A graph $$G=(V,E)$$ G = ( V , E ) is called $$(k,k')$$ ( k , k ′ ) -choosable if the following is true: If each vertex x is assigned a set L(x) of k real numbers, and each edge e is assigned a set L(e) of $$k'$$ k ′ real numbers, then there is a proper total weighting $$\phi $$ ϕ with $$\phi (y)\in L(y)$$ ϕ ( y ) ∈ L ( y ) for any $$y \in V \cup E$$ y ∈ V ∪ E . In this paper, we prove that for any graph $$G\ne K_1$$ G ≠ K 1 , the Mycielski graph of G is (1,4)-choosable. Moreover, we give some sufficient conditions for the Mycielski graph of G to be (1,3)-choosable. In particular, our result implies that if G is a complete bipartite graph, a complete graph, a tree, a subcubic graph, a fan, a wheel, a Halin graph, or a grid, then the Mycielski graph of G is (1,3)-choosable.

Keywords: Total weight choosability; Mycielski graph; Matrix; Permanent; Combinatorial Nullstellensatz (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9943-1 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-9943-1

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

DOI: 10.1007/s10878-015-9943-1

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 ().