Do you want to publish a course? Click here

Every nice graph is $(1,5)$-choosable

104   0   0.0 ( 0 )
 Added by Xuding Zhu
 Publication date 2021
  fields
and research's language is English
 Authors Xuding Zhu




Ask ChatGPT about the research

A graph $G=(V,E)$ is total weight $(k,k)$-choosable if the following holds: For any list assignment $L$ which assigns to each vertex $v$ a set $L(v)$ of $k$ real numbers, and assigns to each edge $e$ a set $L(e)$ of $k$ real numbers, there is a proper $L$-total weighting, i.e., a map $phi: V cup E to mathbb{R}$ such that $phi(z) in L(z)$ for $z in V cup E$, and $sum_{e in E(u)}phi(e)+phi(u) e sum_{e in E(v)}phi(e)+phi(v)$ for every edge ${u,v}$. A graph is called nice if it contains no isolated edges. As a strengthening of the famous 1-2-3 conjecture, it was conjectured in [T. Wong and X. Zhu, Total weigt choosability of graphs, J. Graph Th. 66 (2011),198-212] that every nice graph is total weight $(1,3)$-choosable. The problem whether there is a constant $k$ such that every nice graph is total weight $(1,k)$-choosable remained open for a decade and was recently solved by Cao [L. Cao, Total weight choosability of graphs: Towards the 1-2-3 conjecture, J. Combin. Th. B, 149(2021), 109-146], who proved that every nice graph is total weight $(1, 17)$-choosable. This paper improves this result and proves that every nice graph is total weight $(1, 5)$-choosable.



rate research

Read More

91 - Jin-Xin Zhou 2016
A graph $G$ with a group $H$ of automorphisms acting semiregularly on the vertices with two orbits is called a {em bi-Cayley graph} over $H$. When $H$ is a normal subgroup of $Aut(G)$, we say that $G$ is {em normal} with respect to $H$. In this paper, we show that every finite group has a connected normal bi-Cayley graph. This improves Theorem~5 of [M. Arezoomand, B. Taeri, Normality of 2-Cayley digraphs, Discrete Math. 338 (2015) 41--47], and provides a positive answer to the Question of the above paper.
106 - Huajing Lu , Xuding Zhu 2021
A graph $G$ is total weight $(k,k)$-choosable if for any total list assignment $L$ which assigns to each vertex $v$ a set $L(v)$ of $k$ real numbers, and each edge $e$ a set $L(e)$ of $k$ real numbers, there is a proper total $L$-weighting, i.e., a mapping $f: V(G) cup E(G) to mathbb{R}$ such that for each $z in V(G) cup E(G)$, $f(z) in L(z)$, and for each edge $uv$ of $G$, $sum_{e in E(u)}f(e)+f(u) e sum_{e in E(v)}f(e) + f(v)$. This paper proves that if $G$ decomposes into complete graphs of odd order, then $G$ is total weight $(1,3)$-choosable. As a consequence, every Eulerian graph $G$ of large order and with minimum degree at least $0.91|V(G)|$ is total weight $(1,3)$-choosable. We also prove that any graph $G$ with minimum degree at least $0.999|V(G)|$ is total weight $(1,4)$-choosable.
63 - Changxin Ding 2021
Let $G$ be a ribbon graph. Matthew Baker and Yao Wang proved that the rotor-routing torsor and the Bernardi torsor for $G$, which are two torsor structures on the set of spanning trees for the Picard group of $G$, coincide when $G$ is planar. We prove the conjecture raised by them that the two torsors disagree when $G$ is non-planar.
We present a riemannian structure on the disk that has a remarkably rich structure. Geodesics are hypocycloids and the (negative of the) laplacian has integer spectrum with multiplicity the Dirichlet divisor function. Eigenfunctions of the laplacian are orthogonal polynomials naturally suited to the analysis of acoustic scattering in layered media.
147 - Ilkyoo Choi 2013
The choosability $chi_ell(G)$ of a graph $G$ is the minimum $k$ such that having $k$ colors available at each vertex guarantees a proper coloring. Given a toroidal graph $G$, it is known that $chi_ell(G)leq 7$, and $chi_ell(G)=7$ if and only if $G$ contains $K_7$. Cai, Wang, and Zhu proved that a toroidal graph $G$ without 7-cycles is 6-choosable, and $chi_ell(G)=6$ if and only if $G$ contains $K_6$. They also prove that a toroidal graph $G$ without 6-cycles is 5-choosable, and conjecture that $chi_ell(G)=5$ if and only if $G$ contains $K_5$. We disprove this conjecture by constructing an infinite family of non-4-colorable toroidal graphs with neither $K_5$ nor cycles of length at least 6; moreover, this family of graphs is embeddable on every surface except the plane and the projective plane. Instead, we prove the following slightly weaker statement suggested by Zhu: toroidal graphs containing neither $K^-_5$ (a $K_5$ missing one edge) nor 6-cycles are 4-choosable. This is sharp in the sense that forbidding only one of the two structures does not ensure that the graph is 4-choosable.
comments
Fetching comments Fetching comments
Sign in to be able to follow your search criteria
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا