Edge partitions of optimal 2-plane and 3-plane graphs

A topological graph is a graph drawn in the plane. A topological graph is $k$-plane, $k>0$, if each edge is crossed at most $k$ times. We study the problem of partitioning the edges of a $k$-plane graph such that each partite set forms a graph with a simpler structure. While this problem has been studied for $k=1$, we focus on optimal 2-plane and on optimal 3-plane graphs, which are 2-plane and 3-plane graphs with maximum density. We prove the following results. (i) It is not possible to partition the edges of a simple (i.e., with neither self-loops nor parallel edges) optimal 2-plane graph into a 1-plane graph and a forest, while (ii) an edge partition formed by a 1-plane graph and two plane forests always exists and can be computed in linear time. (iii) There exist efficient algorithms to partition the edges of a simple optimal 2-plane graph into a 1-plane graph and a plane graph with maximum vertex degree at most 12, or with maximum vertex degree at most 8 if the optimal2-plane graph is such that its crossing-free edges form a graph with no separating triangles. (iv) There exists an infinite family of simple optimal 2-plane graphs such that in any edge partition composed of a 1-plane graph and a plane graph, the plane graph has maximum vertex degree at least 6 and the 1-plane graph has maximum vertex degree at least 12. (v) Every optimal 3-plane graph whose crossing-free edges form a biconnected graph can be decomposed, in linear time, into a 2-plane graph and two plane forests.     

Homomorphisms of planar (m,n)-colored-mixed graphs to planar targets

An $(m,n)$-colored-mixed graph $G=(V,A_1,A_2,\cdots ,A_m,E_1,E_2,\cdots ,E_n)$ is a graph having m colors of arcs and n colors of edges. We do not allow two arcs or edges to have the same endpoints. A homomorphism from an $(m,n)$-colored-mixed graph G to another $(m,n)$-colored-mixed graph H is a morphism $\phi :V(G)\to V(H)$ such that each edge (resp. arc) of G is mapped to an edge (resp. arc) of H of the same color (and orientation). An $(m,n)$-colored-mixed graph T is said to be $P_g^{(m,n)}$-universal if every graph in $P_g^{(m,n)}$ (the planar $(m,n)$-colored-mixed graphs with girth at least g) admits a homomorphism to T.We show that planar $P_g^{(m,n)}$-universal graphs do not exist for $2m+n\ge 3$ (and any value of g) and find a minimal (in the number vertices) planar $P_g^{(m,n)}$-universal graphs in the other cases.     

3-list-coloring planar graphs of girth 4

In Thomassen (1995) [4], Thomassen proved that planar graphs of girth at least 5 are 3-choosable. In Li (2009) [3], Li improved Thomassen’s result by proving that planar graphs of girth 4 with no 4-cycle sharing a vertex with another 4- or 5-cycle are 3-choosable. In this paper, we prove that planar graphs of girth 4 with no 4-cycle sharing an edge with another 4- or 5-cycle are 3-choosable. It is clear that our result strengthens Li’s result.     

Colouring of generalized signed triangle-free planar graphs

We view an undirected graph $G$ as a symmetric digraph, where each edge $xy$ is replaced by two opposite arcs $e=(x,y)$ and $e^{?1}=(y,x)$. Assume $S$ is an inverse closed subset of permutations of positive integers. We say $G$ is $S$-$k$-colourable if for any mapping $\sigma :E\left(G\right)\to S$ with $\sigma (x,y)={\left(\sigma (y,x)\right)}^{?1}$, there is a mapping $f:V\left(G\right)\to \left[k\right]=\{1,2,\dots ,k\}$ such that ${\sigma }_e\left(f\left(x\right)\right)\ne f\left(y\right)$ for each arc $e=(x,y)$. The concept of $S$-$k$-colourable is a common generalization of several other colouring concepts. This paper is focused on finding the sets $S$ such that every triangle-free planar graph is $S$-3-colourable. Such a set $S$ is called TFP-good. Grötzsch’s theorem is equivalent to say that $S=\left\{id\right\}$ is TFP-good. We prove that for any inverse closed subset $S$ of $S_3$ which is not isomorphic to $\{id,\left(12\right)\}$, $S$ is TFP-good if and only if either $S=\left\{id\right\}$ or there exists $a\in \left[3\right]$ such that for each $\pi \in S$, $\pi \left(a\right)\ne a$. It remains an open question to determine whether or not $S=\{id,\left(12\right)\}$ is TFP-good.     

On 3-choosable planar graphs of girth at least 4

Let G be a plane graph of girth at least 4. Two cycles of G are intersecting if they have at least one vertex in common. In this paper, we show that if a plane graph G has neither intersecting 4-cycles nor a 5-cycle intersecting with any 4-cycle, then G is 3-choosable, which extends one of Thomassen’s results [C. Thomassen, 3-list-coloring planar graphs of girth 5, J. Combin. Theory Ser. B 64 (1995) 101-107].     

DP-3-coloring of some planar graphs

In this article, we use a unified approach to prove several classes of planar graphs are DP-3-colorable, which extend the corresponding results on 3-choosability.     

The list L(2,1)-labeling of planar graphs

Let $\mathbf{N}$ be the set of all positive integers. A list assignment of a graph $G$ is a function $L:V\left(G\right)?2^{\mathbf{N}}$ that assigns each vertex $v$ a list $L\left(v\right)$ for all $v\in V\left(G\right)$. We say that $G$ is $L$-$(2,1)$-choosable if there exists a function $?$ such that $?\left(v\right)\in L\left(v\right)$ for all $v\in V\left(G\right)$, $|?\left(u\right)??\left(v\right)|\ge 2$ if $u$ and $v$ are adjacent, and $|?\left(u\right)??\left(v\right)|\ge 1$ if $u$ and $v$ are at distance 2. The list-$L(2,1)$-labeling number ${\lambda }_l\left(G\right)$ of $G$ is the minimum $k$ such that for every list assignment $L=\{L\left(v\right):|L\left(v\right)|=k,v\in V\left(G\right)\}$, $G$ is $L$-$(2,1)$-choosable. We prove that if $G$ is a planar graph with girth $g\ge 8$ and its maximum degree $\Delta$ is large enough, then ${\lambda }_l\left(G\right)\le \Delta +3$. There are graphs with large enough $\Delta$ and $g\ge 8$ having ${\lambda }_l\left(G\right)=\Delta +3$.     

On the (3,1)-choosability of planar graphs without adjacent cycles of length 5,6,7

A $(k,d)$-list assignment $L$ of a graph $G$ is a mapping that assigns to each vertex $v$ a list $L\left(v\right)$ of at least $k$ colors satisfying $|L\left(x\right)\cap L\left(y\right)|\le d$ for each edge $xy$. A graph $G$ is $(k,d)$-choosable if there exists an $L$-coloring of $G$ for every $(k,d)$-list assignment $L$. This concept is also known as choosability with separation. In this paper, we prove that any planar graph $G$ is $(3,1)$-choosable if any $i$-cycle is not adjacent to a $j$-cycle, where $5\le i\le 6$ and $5\le j\le 7$.     

Smaller planar triangle-free graphs that are not 3-list-colorable

In 1995, Voigt constructed a planar triangle-free graph that is not 3-list-colorable. It has 166 vertices. Gutner then constructed such a graph with 164 vertices. We present two more graphs with these properties. The first graph has 97 vertices and a failing list assignment using triples from a set of six colors, while the second has 109 vertices and a failing list assignment using triples from a set of five colors.     

Spanning trees with at most 4 leaves in K1,5-free graphs

In 2009, Kyaw proved that every $n$-vertex connected $K_{1,4}$-free graph $G$ with ${\sigma }_4\left(G\right)\ge n?1$ contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected $K_{1,5}$-free graphs. We show that every $n$-vertex connected $K_{1,5}$-free graph $G$ with ${\sigma }_5\left(G\right)\ge n?1$ contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “${\sigma }_5\left(G\right)\ge n?1$” is best possible.     

On the 3-colorability of planar graphs without 4-, 7- and 9-cycles

In this paper, we mainly prove that planar graphs without 4-, 7- and 9-cycles are 3-colorable.     

DP-4-colorability of two classes of planar graphs

DP-coloring (also known as correspondence coloring) is a generalization of list coloring introduced by Dvo?ák and Postle in 2017. In this paper, we prove that every planar graph without 4-cycles adjacent to $k$-cycles is DP-4-colorable for $k=5$ and 6. As a consequence, we obtain two new classes of 4-choosable planar graphs. We use identification of vertices in the proof, and actually prove stronger statements that every pre-coloring of some short cycles can be extended to the whole graph.     

DP-4-colorability of planar graphs without intersecting 5-cycles

DP-coloring of graphs as a generalization of list coloring was introduced by Dvo?ák and Postle (2018). In this paper, we show that every planar graph without intersecting 5-cycles is DP-4-colorable, which improves the result of Hu and Wu (2017), who proved that every planar graph without intersecting 5-cycles is 4-choosable, and the results of Kim and Ozeki (2018).