Search

This paper studies two variants of defective acyclic coloring of planar graphs. For a graph G $G$ and a coloring φ $\varphi $ of G $G$, a 2‐colored cycle (2CC) transversal is a subset E′ ${E}^{^{\prime} }$ of E(G) $E(G)$ that intersects every 2‐colored cycle. Let k $k$ be a positive integer. We denote by mk(G) ${m}_{k}(G)$ the minimum integer m $m$ such that G $G$ has a proper k $k$‐coloring which has a 2CC transversal of size m $m$, and by mk′(G) ${m}_{k}^{^{\prime} }(G)$ the minimum size of a subset E′ ${E}^{^{\prime} }$ of E(G) $E(G)$ such that G−E′ $G-{E}^{^{\prime} }$ is acyclic k $k$‐colorable. We prove that for any n $n$‐vertex 3‐colorable planar graph G,m3(G)≤n−3 $G,{m}_{3}(G)\le n-3$ and for any planar graph G,m4(G)≤n−5 $G,{m}_{4}(G)\le n-5$ provided that n≥5 $n\ge 5$. We show that these upper bounds are sharp: there are infinitely many planar graphs attaining these upper bounds. Moreover, the minimum 2CC transversal E′ ${E}^{^{\prime} }$ can be chosen in such a way that E′ ${E}^{^{\prime} }$ induces a forest. We also prove that for any planar graph G,m3′(G)≤(13n−42)∕10 $G,{m}_{3}^{^{\prime} }(G)\le (13n-42)\unicode{x02215}10$ and m4′(G)≤(3n−12)∕5 ${m}_{4}^{^{\prime} }(G)\le (3n-12)\unicode{x02215}5$. [ABSTRACT FROM AUTHOR]

In this paper, the concept of circular r $r$‐flow in a mono‐directed signed graph (G,σ) $(G,\sigma)$ is introduced. That is a pair (D,f) $(D,f)$, where D $D$ is an orientation on G $G$ and f:E(G)→(−r,r) $f:E(G)\to (-r,r)$ satisfies that ∣f(e)∣∈[1,r−1] $| f(e)| \in [1,r-1]$ for each positive edge e $e$ and ∣f(e)∣∈[0,r2−1]∪[r2+1,r) $| f(e)| \in [0,\frac{r}{2}-1]\cup [\frac{r}{2}+1,r)$ for each negative edge e $e$, and the total in‐flow equals the total out‐flow at each vertex. This is the dual notion of circular colorings of signed graphs and is distinct from the concept of circular flows in bi‐directed graphs associated with signed graphs studied in the literature. We first explore the connection between circular 2kk−1 $\frac{2k}{k-1}$‐flows and modulo k $k$‐orientations in signed graphs. Then we focus on the upper bounds for the circular flow indices of signed graphs in terms of the edge‐connectivity, where the circular flow index of a signed graph is the minimum value r $r$ such that it admits a circular r $r$‐flow. We prove that every 3‐edge‐connected signed graph admits a circular 6‐flow and every 4‐edge‐connected signed graph admits a circular 4‐flow. More generally, for k≥2 $k\ge 2$, we show that every (3k−1) $(3k-1)$‐edge‐connected signed graph admits a circular 2kk−1 $\frac{2k}{k-1}$‐flow, every 3k $3k$‐edge‐connected signed graph has a circular r $r$‐flow with r<2kk−1 $r\lt \frac{2k}{k-1}$, and every (3k+1) $(3k+1)$‐edge‐connected signed graph admits a circular 4k+22k−1 $\frac{4k+2}{2k-1}$‐flow. Moreover, the (6k−2) $(6k-2)$‐edge‐connectivity condition is shown to be sufficient for a signed Eulerian graph to admit a circular 4k2k−1 $\frac{4k}{2k-1}$‐flow, and applying this result to planar graphs, we conclude that every signed bipartite planar graph of negative girth at least 6k−2 $6k-2$ admits a homomorphism to the negative even cycles C−2k ${C}_{-2k}$. [ABSTRACT FROM AUTHOR]

This paper gives a simple proof of the result that every planar graph G $G$ has Alon–Tarsi number at most 5, and has a matching M $M$ such that G−M $G-M$ has Alon–Tarsi number at most 4. [ABSTRACT FROM AUTHOR]

It was conjectured by Ohba, and proved by Noel, Reed and Wu that k $k$‐chromatic graphs G $G$ with ∣V(G)∣≤2k+1 $| V(G)| \le 2k+1$ are chromatic‐choosable. This upper bound on ∣V(G)∣ $| V(G)| $ is tight: if k $k$ is even, then K3⋆(k∕2+1),1⋆(k∕2−1) ${K}_{3\star (k\unicode{x02215}2+1),1\star (k\unicode{x02215}2-1)}$ and K4,2⋆(k−1) ${K}_{4,2\star (k-1)}$ are k $k$‐chromatic graphs with 2k+2 $2k+2$ vertices that are not chromatic‐choosable. It was proved by Zhu and Zhu that these are the only non‐k $k$‐choosable complete k $k$‐partite graphs with 2k+2 $2k+2$ vertices. For G∈{K3⋆(k∕2+1),1⋆(k∕2−1),K4,2⋆(k−1)} $G\in \{{K}_{3\star (k\unicode{x02215}2+1),1\star (k\unicode{x02215}2-1)},{K}_{4,2\star (k-1)}\}$, a bad list assignment of G $G$ is a k $k$‐list assignment L $L$ of G $G$ such that G $G$ is not L $L$‐colourable. Bad list assignments for G=K4,2⋆(k−1) $G={K}_{4,2\star (k-1)}$ were characterized by Enomoto, Ohba, Ota and Sakamoto. In this paper, we first give a simpler proof of this result, and then we characterize bad list assignments for G=K3⋆(k∕2+1),1⋆(k∕2−1) $G={K}_{3\star (k\unicode{x02215}2+1),1\star (k\unicode{x02215}2-1)}$. Using these results, we characterize all non‐k $k$‐choosable k $k$‐chromatic graphs with 2k+2 $2k+2$ vertices. [ABSTRACT FROM AUTHOR]

Assume k $k$ is a positive integer, λ={k1,k2,...,kq} $\lambda =\{{k}_{1},{k}_{2},\ldots ,{k}_{q}\}$ is a partition of k $k$ and G $G$ is a graph. A λ $\lambda $‐assignment of G $G$ is a k $k$‐assignment L $L$ of G $G$ such that the colour set ⋃v∈V(G)L(v) ${\bigcup }_{v\in V(G)}L(v)$ can be partitioned into q $q$ subsets C1∪C2∪⋯∪Cq ${C}_{1}\cup {C}_{2}\cup \cdots \,\cup {C}_{q}$ and for each vertex v $v$ of G $G$, ∣L(v)∩Ci∣=ki $| L(v)\cap {C}_{i}| ={k}_{i}$. We say G $G$ is λ $\lambda $‐choosable if for each λ $\lambda $‐assignment L $L$ of G $G$, G $G$ is L $L$‐colourable. In particular, if λ={k} $\lambda =\{k\}$, then λ $\lambda $‐choosable is the same as k $k$‐choosable, and if λ={1,1,...,1} $\lambda =\{1,1,\ldots ,1\}$, then λ $\lambda $‐choosable is equivalent to k $k$‐colourable. For the other partitions of k $k$ sandwiched between {k} $\{k\}$ and {1,1,...,1} $\{1,1,\ldots ,1\}$ in terms of refinements, λ $\lambda $‐choosability reveals a complex hierarchy of colourability of graphs. Assume λ={k1,...,kq} $\lambda =\{{k}_{1},\ldots ,{k}_{q}\}$ is a partition of k $k$ and λ′ $\lambda ^{\prime} $ is a partition of k′≥k $k^{\prime} \ge k$. We write λ≤λ′ $\lambda \le \lambda ^{\prime} $ if there is a partition λ″={k1″,...,kq″} $\lambda ^{\prime\prime} =\{{k}_{1}^{^{\prime\prime} },\ldots ,{k}_{q}^{^{\prime\prime} }\}$ of k′ $k^{\prime} $ with ki″≥ki ${k}_{i}^{^{\prime\prime} }\ge {k}_{i}$ for i=1,2,...,q $i=1,2,\ldots ,q$ and λ′ $\lambda ^{\prime} $ is a refinement of λ″ $\lambda ^{\prime\prime} $. It follows from the definition that if λ≤λ′ $\lambda \le \lambda ^{\prime} $, then every λ $\lambda $‐choosable graph is λ′ $\lambda ^{\prime} $‐choosable. It was proved in Zhu that the converse is also true. This paper strengthens this result and proves that for any λ≰λ′ $\lambda \,\le \unicode{x00338}\,\lambda ^{\prime} $, for any integer g $g$, there exists a graph of girth at least g $g$ which is λ $\lambda $‐choosable but not λ′ $\lambda ^{\prime} $‐choosable. [ABSTRACT FROM AUTHOR]