Search

Given positive integers p ≥ k $p\ge k$, and a nonnegative integer d $d$, we say a graph G $G$ is ( k , d , p ) $(k,d,p)$‐choosable if for every list assignment L $L$ with ∣ L ( v ) ∣ ≥ k $| L(v)| \ge k$ for each v ∈ V ( G ) $v\in V(G)$ and ∣ ⋃ v ∈ V ( G ) L ( v ) ∣ ≤ p $| {\bigcup }_{v\in V(G)}L(v)| \le p$, there exists an L $L$‐coloring of G $G$ such that each monochromatic subgraph has maximum degree at most d $d$. In particular, ( k , 0 , k ) $(k,0,k)$‐choosable means k $k$‐colorable, ( k , 0 , + ∞ ) $(k,0,+\infty )$‐choosable means k $k$‐choosable and ( k , d , + ∞ ) $(k,d,+\infty )$‐choosable means d $d$‐defective k $k$‐choosable. This paper proves that there are 1‐defective 3‐choosable planar graphs that are not 4‐choosable, and for any positive integers ℓ ≥ k ≥ 3 $\ell \ge k\ge 3$, and nonnegative integer d $d$, there are ( k , d , ℓ ) $(k,d,\ell )$‐choosable graphs that are not ( k , d , ℓ + 1 ) $(k,d,\ell +1)$‐choosable. These results answer questions asked by Wang and Xu, and Kang, respectively. Our construction of ( k , d , ℓ ) $(k,d,\ell )$‐choosable but not ( k , d , ℓ + 1 ) $(k,d,\ell +1)$‐choosable graphs generalizes the construction of Král' and Sgall for the case d = 0 $d=0$. [ABSTRACT FROM AUTHOR]

A homomorphism of a signed graph (G,σ) $(G,\sigma)$ to (H,π) $(H,\pi)$ is a mapping of vertices and edges of G $G$ to (respectively) vertices and edges of H $H$ such that adjacencies, incidences, and the signs of closed walks are preserved. We observe in this work that, for k≥3 $k\ge 3$, the k $k$‐coloring problem of a given graph G $G$ can be captured by homomorphism to (K2k,σm) $({K}_{2k},{\sigma }_{m})$ from a signed bipartite graph that is built from G $G$. Here σm ${\sigma }_{m}$ assigns a negative sign to the edges of a perfect matching and a positive sign to the rest. Motivated by these reformulations and in connection with results on 3‐colorings of planar graphs, such as Grötzsch's theorem, we prove that any signed graph with the maximum average degree strictly less than 145 $\frac{14}{5}$ admits a homomorphism to (K6,σm) $({K}_{6},{\sigma }_{m})$. For k≥4 $k\ge 4$, we show that the maximum average degree being strictly less than 3 would suffice for a signed graph to admit a homomorphism to (K2k,σm) $({K}_{2k},{\sigma }_{m})$. Both of these bounds are tight. We discuss applications of our work to signed planar graphs and its connection to the study of homomorphisms of 2‐edge‐colored graphs. Among a number of interesting questions that are left open, a notable one is a possible extension of Steinberg's conjecture for the class of signed bipartite planar graphs. [ABSTRACT FROM AUTHOR]

A graph G $G$ is called 3‐choice‐critical if G $G$ is not 2‐choosable but any proper subgraph of G $G$ is 2‐choosable. A graph G $G$ is strongly fractional r $r$‐choosable if G $G$ is (a,b) $(a,b)$‐choosable for all positive integers a,b $a,b$ for which a∕b≥r $a\unicode{x02215}b\ge r$. The strong fractional choice number of G $G$ is chfs(G)=inf{r:G $c{h}_{f}^{s}(G)=\text{inf}\{r:G$ is strongly fractional r $r$‐choosable} $\}$. This paper determines the strong fractional choice number of all 3‐choice‐critical graphs. [ABSTRACT FROM AUTHOR]

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 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 et al. in 2017. They showed that if G=Θr,s,t where r,s,t have the same parity and min{r,s,t}≥3, or G=Θ2,2,2,2p with p≥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 show that all the other bipartite 3‐choice critical graphs are (4m,2m)‐choosable for every integer m. [ABSTRACT FROM AUTHOR]

Abstract This paper introduces a new variant of the game Nim–Bounded Greedy Nim. This game is a combination of Bounded Nim and Greedy Nim. We present a complete solution to this game, which generalizes the solution of Greedy Nim. [ABSTRACT FROM AUTHOR]

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 ) → N is a mapping. For a nonnegative integer m , let f ( m ) be the extension of f to the graph G K m ¯ for which f ( m ) ( v ) = | V ( G ) | for each vertex v of K m ¯ . Let m c ( G , f ) be the minimum m such that G K m ¯ is not f ( m ) -choosable and m p ( G , f ) be the minimum m such that G 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 x → = ( x 1 , x 2 , … , x n ) , an x → -dominated path ending at ( a , b ) is a monotonic path P of the a × b grid from ( 0 , 0 ) to ( a , b ) such that each vertex ( i , j ) on P satisfies i ≤ x j + 1 . Let ψ ( x → ) be the number of x → -dominated paths ending at ( x n , n ) . By this definition, the Catalan number C n equals ψ ( ( 0 , 1 , … , n − 1 ) ) . This paper proves that if G = K n has vertices v 1 , v 2 , … , v n and f ( v 1 ) ≤ f ( v 2 ) ≤ … ≤ f ( v n ) , then m c ( G , f ) = m p ( G , f ) = ψ ( x → ( f ) ) , where x → ( f ) = ( x 1 , x 2 , … , x n ) and x i = f ( v i ) − i for i = 1 , 2 , … , n . Therefore, if f ( v i ) = n , then m c ( K n , f ) = m p ( K n , f ) equals the Catalan number C n . We also show that if G = G 1 ∪ G 2 ∪ ⋯ ∪ G p is the disjoint union of graphs G 1 , G 2 , … , G p and f = f 1 ∪ f 2 ∪ ⋯ ∪ f p , then m c ( G , f ) = ∏ i = 1 p m c ( G i , f i ) and m p ( G , f ) = ∏ i = 1 p m p ( G i , f i ) . This generalizes a result in Carraher et al. (2014), where the case each G i is a copy of K 1 is considered. [ABSTRACT FROM AUTHOR]

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