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 m
apping $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.
Assume $ k $ is a positive integer, $ lambda={k_1,k_2,...,k_q} $ is a partition of $ k $ and $ G $ is a graph. A $lambda$-assignment of $ G $ is a $ k $-assignment $ L $ of $ G $ such that the colour set $ bigcup_{vin V(G)} L(v) $ can be partitioned
into $ q $ subsets $ C_1cup C_2cupcdotscup C_q $ and for each vertex $ v $ of $ G $, $ |L(v)cap C_i|=k_i $. We say $ G $ is $lambda$-choosable if for each $lambda$-assignment $ L $ of $ G $, $ G $ is $ L $-colourable. In particular, if $ lambda={k} $, then $lambda$-choosable is the same as $ k $-choosable, if $ lambda={1, 1,...,1} $, then $lambda$-choosable is equivalent to $ k $-colourable. For the other partitions of $ k $ sandwiched between $ {k} $ and $ {1, 1,...,1} $ in terms of refinements, $lambda$-choosability reveals a complex hierarchy of colourability of graphs. Assume $lambda={k_1, ldots, k_q} $ is a partition of $ k $ and $lambda $ is a partition of $ kge k $. We write $ lambdale lambda $ if there is a partition $lambda={k_1, ldots, k_q}$ of $k$ with $k_i ge k_i$ for $i=1,2,ldots, q$ and $lambda$ is a refinement of $lambda$. It follows from the definition that if $ lambdale lambda $, then every $lambda$-choosable graph is $lambda$-choosable. It was proved in [X. Zhu, A refinement of choosability of graphs, J. Combin. Theory, Ser. B 141 (2020) 143 - 164] that the converse is also true. This paper strengthens this result and proves that for any $ lambda otle lambda $, for any integer $g$, there exists a graph of girth at least $g$ which is $lambda$-choosable but not $lambda$-choosable.
Assume $n, m$ are positive integers and $G$ is a graph. Let $P_{n,m}$ be the graph obtained from the path with vertices ${-m, -(m-1), ldots, 0, ldots, n}$ by adding a loop at vertex $ 0$. The double cone $Delta_{n,m}(G)$ over a graph $G$ is obtained
from the direct product $G times P_{n,m}$ by identifying $V(G) times {n}$ into a single vertex $(star, n)$, identifying $V(G) times {-m}$ into a single vertex $(star, -m)$, and adding an edge connecting $(star, -m)$ and $(star, n)$. This paper determines the fractional chromatic number of $Delta_{n,m}(G)$. In particular, if $n < m$ or $n=m$ is even, then $chi_f(Delta_{n,m}(G)) = chi_f(Delta_n(G))$, where $Delta_n(G)$ is the $n$th cone over $G$. If $n=m$ is odd, then $chi_f(Delta_{n,m}(G)) > chi_f(Delta_n(G))$. The chromatic number of $Delta_{n,m}(G)$ is also discussed.
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 prope
r $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.
A graph $G$ is called $3$-choice critical if $G$ is not $2$-choosable but any proper subgraph is $2$-choosable. A graph $G$ is strongly fractional $r$-choosable if $G$ is $(a,b)$-choosable for all positive integers $a,b$ for which $a/b ge r$. The str
ong fractional choice number of $G$ is $ch_f^s(G) = inf {r: G $ is strongly fractional $r$-choosable$}$. This paper determines the strong fractional choice number of all $3$-choice critical graphs.
A signed graph is a pair $(G, sigma)$, where $G$ is a graph and $sigma: E(G) to {+, -}$ is a signature which assigns to each edge of $G$ a sign. Various notions of coloring of signed graphs have been studied. In this paper, we extend circular colorin
g of graphs to signed graphs. Given a signed graph $(G, sigma)$ a circular $r$-coloring of $(G, sigma)$ is an assignment $psi$ of points of a circle of circumference $r$ to the vertices of $G$ such that for every edge $e=uv$ of $G$, if $sigma(e)=+$, then $psi(u)$ and $psi(v)$ have distance at least $1$, and if $sigma(e)=-$, then $psi(v)$ and the antipodal of $psi(u)$ have distance at least $1$. The circular chromatic number $chi_c(G, sigma)$ of a signed graph $(G, sigma)$ is the infimum of those $r$ for which $(G, sigma)$ admits a circular $r$-coloring. For a graph $G$, we define the signed circular chromatic number of $G$ to be $max{chi_c(G, sigma): sigma text{ is a signature of $G$}}$. We study basic properties of circular coloring of signed graphs and develop tools for calculating $chi_c(G, sigma)$. We explore the relation between the circular chromatic number and the signed circular chromatic number of graphs, and present bounds for the signed circular chromatic number of some families of graphs. In particular, we determine the supremum of the signed circular chromatic number of $k$-chromatic graphs of large girth, of simple bipartite planar graphs, $d$-degenerate graphs, simple outerplanar graphs and series-parallel graphs. We construct a signed planar simple graph whose circular chromatic number is $4+frac{2}{3}$. This is based and improves on a signed graph built by Kardos and Narboni as a counterexample to a conjecture of M{a}v{c}ajov{a}, Raspaud, and v{S}koviera.
A graph $G$ is called $3$-choice critical if $G$ is not $2$-choosable but any proper subgraph is $2$-choosable. A characterization of $3$-choice critical graphs was given by Voigt in [On list Colourings and Choosability of Graphs, Habilitationsschrif
t, Tu Ilmenau(1998)]. Voigt conjectured that if $G$ is a bipartite $3$-choice critical graph, then $G$ is $(4m, 2m)$-choosable for every integer $m$. This conjecture was disproved by Meng, Puleo and Zhu in [On (4, 2)-Choosable Graphs, Journal of Graph Theory 85(2):412-428(2017)]. They showed that if $G=Theta_{r,s,t}$ where $r,s,t$ have the same parity and $min{r,s,t} ge 3$, or $G=Theta_{2,2,2,2p}$ with $p ge 2$, then $G$ is bipartite $3$-choice critical, but not $(4,2)$-choosable. On the other hand, all the other bipartite 3-choice critical graphs are $(4,2)$-choosable. This paper strengthens the result of Meng, Puleo and Zhu and shows that all the other bipartite $3$-choice critical graphs are $(4m,2m)$-choosable for every integer $m$.
Hedetniemi conjectured in 1966 that $chi(G times H) = min{chi(G), chi(H)}$ for all graphs $G$ and $H$. Here $Gtimes H$ is the graph with vertex set $ V(G)times V(H)$ defined by putting $(x,y)$ and $(x,y)$ adjacent if and only if $xxin E(G)$ and $yyin
E(H)$. This conjecture received a lot of attention in the past half century. Recently, Shitov refuted this conjecture. Let $p$ be the minimum number of vertices in a graph of odd girth $7$ and fractional chromatic number greater than $3+4/(p-1)$. Shitovs proof shows that Hedetniemis conjecture fails for some graphs with chromatic number about $p^22^{p+1} $ and with about $(p^22^{p+1})^{p^32^{p-1}} $ vertices. In this paper, we show that the conjecture fails already for some graphs $G$ and $H$ with chromatic number $3lceil frac {p+1}2 rceil $ and with $p lceil (p-1)/2 rceil$ and $3 lceil frac {p+1}2 rceil (p+1)-p$ vertices, respectively. The currently known upper bound for $p$ is $148$. Thus Hedetniemis conjecture fails for some graphs $G$ and $H$ with chromatic number $225$, and with $10,952$ and $33,377$ vertices, respectively.
