Search

Given positive integers $p \ge k$, and a non-negative integer $d$, we say a graph $G$ is $(k,d,p)$-choosable if for every list assignment $L$ with $|L(v)|\geq k$ for each $v \in V(G)$ and $|\bigcup_{v\in V(G)}L(v)| \leq p$, there exists an $L$-coloring of $G$ such that each monochromatic subgraph has maximum degree at most $d$. In particular, $(k,0,k)$-choosable means $k$-colorable, $(k,0,+\infty)$-choosable means $k$-choosable and $(k,d,+\infty)$-choosable means $d$-defective $k$-choosable. This paper proves that there are 1-defective 3-choosable graphs that are not 4-choosable, and for any positive integers $\ell \geq k \geq 3$, and non-negative integer $d$, there are $(k,d, \ell)$-choosable graphs that are not $(k,d , \ell+1)$-choosable. These results answer questions asked by Wang and Xu [SIAM J. Discrete Math. 27, 4(2013), 2020-2037], and Kang [J. Graph Theory 73, 3(2013), 342-353], respectively. Our construction of $(k,d, \ell)$-choosable but not $(k,d , \ell+1)$-choosable graphs generalizes the construction of Kr\'{a}l' and Sgall in [J. Graph Theory 49, 3(2005), 177-186] for the case $d=0$., Comment: 12 pages, 4 figures

A decomposition of a graph $G$ is a family of subgraphs of $G$ whose edge sets form a partition of $E(G)$. In this paper, we prove that every triangle-free planar graph $G$ can be decomposed into a $2$-degenerate graph and a matching. Consequently, every triangle-free planar graph $G$ has a matching $M$ such that $G-M$ is online 3-DP-colorable. This strengthens an earlier result in [R. \v{S}krekovski, {\em A Gr\"{o}tzsch-Type Theorem for List Colourings with Impropriety One}, Combin. Prob. Comput. 8 (1999), 493-507] that every triangle-free planar graph is $1$-defective $3$-choosable.

We propose a systematic method based on reinforcement learning (RL) techniques to find the optimal path that can minimize the total entropy production between two equilibrium states of open systems at the same temperature in a given fixed time period. Benefited from the generalization of the deep RL techniques, our method can provide a powerful tool to address this problem in quantum systems even with two-dimensional continuous controllable parameters. We successfully apply our method on the classical and quantum two-level systems., Comment: 13 pages, 4 figures

A \emph{signed graph} $(G, \sigma)$ is a graph $G$ together with an assignment $\sigma:E(G) \rightarrow \{+,-\}$. The notion of homomorphisms of signed graphs is a relatively new development which allows to strengthen the connection between the theories of minors and colorings of graphs. Following this thread of thoughts, we investigate this connection through the notion of Extended Double Covers of signed graphs, which was recently introduced by Naserasr, Sopena and Zaslavsky. More precisely, we say that a signed graph $(B, \pi)$ is planar-complete if any planar signed graph $(G, \sigma)$ which verifies the conditions of a basic no-homomorphism lemma with respect to $(B,\pi)$ admits a homomorphism to $(B, \pi)$. Our conjecture then is that: if $(B, \pi)$ is a connected signed graph with no positive odd closed walk which is planar-complete, then its Extended Double Cover ${\rm EDC}(B,\pi)$ is also planar-complete. We observe that this conjecture largely extends the Four-Color Theorem and is strongly connected to a number of conjectures in extension of this famous theorem. A given (signed) graph $(B,\pi)$ \emph{bounds} a class of (signed) graphs if every (signed) graph in the class admits a homomorphism to $(B,\pi)$. In this work, and in support of our conjecture, we prove it for the subclass of signed $K_4$-minor free graphs. Inspired by this development, we then investigate the problem of finding optimal homomorphism bounds for subclasses of signed $K_4$-minor-free graphs with restrictions on their girth and we present nearly optimal solutions. Our work furthermore leads to the development of weighted signed graphs., Comment: 20 pages, 3 figures

This paper studies the strong fractional choice number $ch^s_f(G)$ and the strong fractional paint number $\chi^s_{f,P}(G)$ of a graph $G$. We prove that these parameters of any finite graph are rational numbers. On the other hand, for any positive integers $p,q$ satisfying $2 \le \frac{2p}{2q+1} \leq \lfloor\frac{p}{q}\rfloor$, there exists a graph $G$ with $ch^s_f(G) = \chi^s_{f,P}(G) = \frac{p}{q}$. The relationship between $\chi^s_{f,P}(G)$ and $ch^s_f(G)$ is explored. We prove that the gap $\chi^s_{f,P}(G)-ch^s_f(G)$ can be arbitrarily large. The strong fractional choice number of a family $\mathcal{G}$ of graphs is the supremum of the strong fractional choice number of graphs in $\mathcal{G}$. Let $\mathcal{P}$ denote the class of planar graphs and $\mathcal{P}_{k_1,\ldots, k_q}$ denote the class of planar graphs without $k_i$-cycles for $i=1,\ldots, q$. We prove that $3 + \frac{1}{2} \leq ch^s_f(\mathcal{P}_{ 4}) \leq 4$, $ch^s_f(\mathcal{P}_{ k})=4$ for $k \in \{5,6\}$, $3 +\frac{1}{12} \leq ch^s_f(\mathcal{P}_{ 4,5}) \leq 4$ and $ch^s_f(\mathcal{P}) \ge 4+\frac 13$. The last result improves the lower bound $4+\frac 29$ in [X. Zhu, multiple list colouring of planar graphs, Journal of Combin. Th. Ser. B,122(2017),794-799]., Comment: 20 pages,6 figures

Heat engines are fundamental physical objects to develop nonequilibrium thermodynamics. The thermodynamic performance of the heat engine is determined by the choice of cycle and time-dependence of parameters. Here, we propose a systematic numerical method to find a heat engine cycle to optimize some target functions. We apply the method to heat engines with slowly varying parameters and show that the method works well. Our numerical method is based on the genetic algorithm which is widely applied to various optimization problems., Comment: 29 pages, 6 figures

A homomorphism of a signed graph $(G, \sigma)$ to $(H, \pi)$ is a mapping of vertices and edges of $G$ to (respectively) vertices and edges of $H$ such that adjacencies, incidences and the product of signs of closed walks are preserved. Motivated by reformulations of the $k$-coloring problem in this language, and specially in connection with results on $3$-coloring of planar graphs, such as Gr\"otzsch's theorem, in this work we consider bounds on maximum average degree which are sufficient for mapping to the signed graph $(K_{2k}, \sigma_m)$ ($k\geq 3$) where $\sigma_m$ assigns to edges of a perfect matching the negative sign. For $k=3$, we show that the maximum average degree strictly less than $\frac{14}{5}$ is sufficient and that this bound is tight. For all values of $k\geq 4$, we find the best maximum average degree bound to be 3. While the homomorphisms of signed graphs is relatively new subject, through the connection with the homomorphisms of $2$-edge-colored graphs, which are largely studied, some earlier bounds are already given. In particular, it is implied from Theorem 2.5 of "Borodin, O. V., Kim, S.-J., Kostochka, A. V., and West, D. B., Homomorphisms from sparse graphs with large girth. J. Combin. Theory Ser. B (2004)" that if $G$ is a graph of girth at least 7 and maximum average degree $\frac{28}{11}$, then for any signature $\sigma$ the signed graph $(G,\sigma)$ maps to $(K_6, \sigma_m)$. We discuss applications of our work to signed planar graphs and, among others, we propose questions similar to Steinberg's conjecture for the class of signed bipartite planar graphs.

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 strong 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., Comment: 29 pages. arXiv admin note: text overlap with arXiv:2006.15614

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, Habilitationsschrift, 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$., Comment: 18 pages, 2 figures

In this Letter, we present a new strategy for applying the learning machine to study phase transitions. We train the learning machine with samples only obtained at a non-critical parameter point, aiming to establish intrinsic correlations between the learning machine and the target system. Then, we find that the accuracy of the learning machine, which is the most important performance index in conventional learning machines, is no longer a key goal of the training in our approach. Instead, relatively low accuracy of identifying unlabeled data category can help to determine the critical point with greater precision, manifesting the singularity around the critical point. It thus provides a robust tool to study the phase transition. The classical ferromagnetic and percolation phase transitions are employed as illustrative examples., Comment: 5 pages, 5 figures

The Catalan numbers occur in various counting problems in combinatorics. This paper reveals a connection between the Catalan numbers and list colouring of graphs. Assume $G$ is a graph and $f:V(G) \to N$ is a mapping. For a nonnegative integer $m$, let $f^{(m)}$ be the extension of $f$ to the graph $ G \diamondplus \overline{K_m}$ for which $f^{(m)}(v)=|V(G)|$ for each vertex $v$ of $\overline{K_m}$. Let $m_c(G,f)$ be the minimum $m$ such that $ G \diamondplus \overline{K_m}$ is not $f^{(m)}$-choosable and $m_p(G,f)$ be the minimum $m$ such that $ G \diamondplus \overline{K_m}$ is not $f^{(m)}$-paintable. We study the parameter $m_c(K_n, f)$ and $m_p(K_n,f)$ for arbitrary mappings $f$. For $\vec{x}=(x_1,x_2,\ldots,x_n)$, an $\vec{x}$-dominated path ending at $(a, b)$ is a monotonic path $P$ of the $a \times b$ grid from $(0,0)$ to $(a,b)$ such that each vertex $(i,j)$ on $P$ satisfies $i \le x_{j+1}$. Let $\psi(\vec{x})$ be the number of $\vec{x}$-dominated paths ending at $(x_n,n)$. By this definition, the Catalan number $C_n$ equals $ \psi((0,1, \ldots, n-1)) $. This paper proves that if $G=K_n$ has vertices $v_1, v_2, \ldots, v_n$ and $f(v_1) \le f(v_2) \le \ldots \le f(v_n)$, then $m_c(G,f)=m_p(G,f)=\psi(\vec{x}(f))$, where $\vec{x}(f)=(x_1, x_2, \ldots, x_n)$ and $x_i=f(v_i)-i$ for $i=1, 2,\ldots, n$. Therefore, if $f(v_i)=n$, then $m_c(K_n, f)=m_p(K_n, f)$ equals the Catalan number $C_n$., Comment: 16 pages, 3 figures