Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable
Seog-Jin Kim Xiaowei Yu
math.CO







Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable
    
Seog-Jin KimDepartment of Mathematics Education, Konkuk University,
Korea. Email: skim12@konkuk.ac.kr

Supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education(NRF-2015R1D1A1A01057008).
and
Xiaowei YuSchool of Mathematics, Shandong University, Jinan, Shandong, 250100, P. R. China. Corresponding author.
Email: xwyu2013@163.com
Supported by the National Natural Science Foundation of China (11371355,
11471193, 11271006, 11631014), the Foundation for Distinguished Young Scholars of Shandong Province
(JQ201501), and fundamental research funding of Shandong University.



    December 30, 2023
===============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




DP-coloring (also known as correspondence coloring) of a simple graph is
a generalization of list coloring.

It is known that planar graphs without 4-cycles adjacent to triangles are 4-choosable, and planar graphs without 4-cycles are DP-4-colorable. In this paper, we show that  planar graphs without 4-cycles adjacent to triangles are DP-4-colorable, which is an extension of the two results above.




Keywords:
Coloring,
list-coloring,
DP-coloring,
signed graph





§ INTRODUCTION





We use standard notation. For a set S, Pow(S) denote the power set of S, i.e., the set of all subsets of S. We denote by [k] the set of integers from 1 to k. All graphs considered here are finite, undirected, and simple. For a graph G, V(G), E(G), and F(G) denote the vertex sets, edge sets and face sets of G, respectively. For a set U⊆ V(G), G[U] is the subgraph of G induced by U.







Recall that a proper k-coloring of a graph G
is a mapping f : V(G) → [k]
such that f(u) ≠ f(v) for any uv ∈ E(G).



The minimum integer k
such that G admits a proper coloring
is called the chromatic number of G,
and denoted by χ(G).

List coloring is a generalization of graph coloring that was introduced independently by Vizing <cit.> and Erdős, Rubin, and Taylor <cit.>.
Let C be a set of colors.
A list assignment L : V(G) → Pow(C) of G
is a mapping that assigns a set of colors to each vertex. If |L(v)|≥ k for all v∈ V(G), then L is called a k-list assignment.
A proper coloring f: V(G) → C is called an L-coloring of G if
f(u) ∈ L(u) for any u ∈ V(G). The list-chromatic number or the choice number of G, denoted by χ_ℓ(G), is the smallest k such that G admits an L-coloring for every k-list assignment L for G.














Since a proper k-coloring corresponds to an L-coloring
with L(u) = [k] for any u ∈ V(G),
we have χ(G) ≤χ_ℓ(G).
It is well-known that
there are infinitely many graphs G
satisfying χ (G) < χ_ℓ(G),
and the gap can be  arbitrarily large.












In order to consider some problems on list chromatic number,
Dvořák and Postle <cit.> considered
a generalization of a list coloring.
They call it a correspondence coloring,
but we call it a DP-coloring for short,
following Bernshteyn, Kostochka and Pron <cit.>.


Let G be a  graph
and L be a list assignment of G.
For each edge uv in G,
let M_L,uv be an arbitrary matching (maybe empty)
between {u}× L(u) and {v}× L(v).
Without abuse of notation,
we sometimes regard M_L,uv
as a bipartite graph in which the edges are
between {u}× L(u) and {v}× L(v), and
the maximum degree is at most 1.




Let _L = {M_L,uv : uv ∈ E(G) },
which is called a matching assignment over L.
Then a graph H is said to be the _L-cover of G
if it satisfies all the following conditions:


  * The vertex set of H is
⋃_u ∈ V(G)({u}× L(u))
= {(u,c): u ∈ V(G),  c ∈ L(u)}.


  * For every u ∈ V(G),
the graph H[{u}× L(u)] is a clique.

  * For any edge uv in G,
{u}× L(u)
and
{v}× L(v)
induce the graph obtained from M_L,uv in H.







An _L-coloring of G is an independent set I in
the _L-cover with |I| = |V(G)|.
The DP-chromatic number,
denoted by χ_DP(G),
is the minimum integer k
such that G admits an _L-coloring
for each k-list assignment L and each matching assignment _L over L.  We say that a graph G is DP-k-colorable if χ_DP(G) ≤ k.


Note that
when G is a simple graph and

    M_L,uv = {(u,c)(v,c): c ∈ L(u) ∩ L(v)
    }

for any edge uv in G,
then G admits an L-coloring
if and only if
G admits an _L-coloring.
This implies χ_ℓ(G) ≤χ_DP(G). Thus DP-coloring is a generalization of the list coloring. Thus, given the fact χ_ℓ (G) ≤ k, it is interesting to check whether χ_DP(G) ≤ k or not.

Dvořák and Postle <cit.> showed that χ_DP(G) ≤ 5 if G is a  planar graph, and χ_DP(G) ≤ 3 if G is a planar graph with girth at least 5.
Also, Dvořák and Postle <cit.> observed that χ_DP(G) ≤ k+1 if G is k-degenerate.

On the other hand, there are some differences between DP-coloring and list coloring.
There are infinitely many simple graphs G
satisfying χ_ℓ (G) < χ_DP(G):
It is known that
χ(C_n) = χ_ℓ(C_n) = 2 < 3 = χ_DP(C_n)
for each even integer n ≥ 4 (see <cit.>).
Furthermore,
the gap χ_DP(G) - χ_ℓ (G)
can be arbitrary large.
For example,
Bernshteyn <cit.> showed that
for a simple graph G with average degree d,
we have χ_DP(G) = Ω(d / log d),
while Alon <cit.> proved
that χ_ℓ(G) = Ω(log d) and
the bound is sharp.
Recently, there are some other works on DP-colorings,
see <cit.>.







Thomassen <cit.> showed that every planar graph is 5-choosable, and Voigt <cit.> showed that there are planar graphs which are not 4-choosable.
Thus finding sufficient conditions for planar graphs to be 4-choosable is an interesting problem.


Two faces are adjacent if they have at least one common edge, and two faces are normally adjacent if they are adjacent and have exactly one common edge.
Let C_k be the cycle of length k.
Lam, Xu, and Liu <cit.> verified that every planar graph without C_4 is 4-choosable.  And Cheng, and Chen, Wang <cit.>, and Kim and Ozeki <cit.> extended the result independently by certifying the following theorem.

 The following results hold independently.

  
  A. (<cit.>) If G is a planar graph without 4-cycles adjacent to 3-cycles, then χ_ℓ(G)≤ 4.
  
  B. (<cit.>) If G is a planar graph without 4-cycles, then χ_DP(G)≤ 4.





In this paper, we extend Theorem <ref> by proving
the following theorem.

  If G is a planar graph without 4-cycles adjacent to 3-cycles, then χ_DP (G) ≤ 4.



Even though χ_DP (G)=χ_ℓ(G) for some special graphs, Theorem <ref> is not trivial from Theorem <ref> (A). We will give an explanation in section 3.1.











§ PROOF OF THEOREM <REF>




Suppose that Theorem <ref> does not hold.
In the rest of paper, let G be a minimal counterexample to Theorem <ref> with fewest edges. From our hypothesis, graph G has the following properties:


  * G is connected; and

  * G has no subgraph isomorphic to 4-cycles adjacent to 3-cycles; and

  * G is not DP-4-colorable; and

  * any proper subgraph G' of G is DP-4-colorable.


Embedding G into a plane, we obtain a plane graph G=(V,E,F)
where V,E,F are the sets of vertices, edges, and faces of G,
respectively.

For a vertex v∈ V, the degree of v in G is
denoted by d_G(v).  A vertex of degree d (at least d, at most d, respectively) is called a d-vertex (d^+-vertex, d^--vertex, respectively). The notions of d-face, d^+-face, d^--face are similarly defined. According to (b), if a 5-face is adjacent to a 3-face, then they are normally adjacent.

For a face f∈ F, if the vertices on f in a cyclic order are v_1, v_2, …, v_k, then we write f= [v_1 v_2 ⋯ v_kv_1], and call f a (d_G(v_1), d_G(v_2), …, d_G(v_k) )-face.




 §.§ Structures


Using the properties of G above, we can obtain several local structures of G.

  Graph G has no 3^--vertex.



Suppose to the contrary that there exists a 3^--vertex w in G. Let L be a list assignment of G with |L(v)|≥ 4 for any v∈ V, and let _L be a matching assignment over L. Let G': = G -{ w} and L'(v)=L(v) for v∈ V(G'). According to (d), G' admits an _L'-coloring.
Thus there is an independent set I' in _L'-cover with |I'| = |V(G)| - 1.
For w, we define that

    L^*(w) = L(w) ∖⋃_uw ∈ E(G){c' ∈ L(w): (u,c)(w,c') ∈ M_L,uw (u, c) ∈ I' }.

Since |L(w)| ≥ 4 and w is a 3^--vertex, we have that |L^*(w)| ≥ 1. We denote by _L^* the restriction of _L into G[w] and L^*. Obviously, I=I'∪{{w}× L^*(w)} is an independent set in the _L^*-cover with |I| = |V(G)|, which is a contradiction to (c).





 Next we define several different 5-faces.
Let f be a 5-face of G.




  * If f is a (4,4,4,4,4)-face, then we call f a small 5-face. Assume that f is adjacent to a 3-face f'=[vv_1v_2v] with the common edge v_1v_2, then we call v a source of f. Equivalently, the face f is called a sink of v (see F_1 in Figure <ref>).



  * If f is a (5^+,4,4,4,4)-face, and f is incident to four 3-faces and one 4^+-face, and the 4^+-face is incident to the 5^+-vertex on f, then we call f a bad 5-face (see F_2 in Figure <ref>).



  * If f is a (5^+,4,4,4,4)-face, and f is incident to five 3-faces, then we call f a special 5-face. Meanwhile, we call the 5^+-vertex on f a special vertex (see F_3 in Figure <ref>).





  * A special vertex is incident to at least one special 5-face, and a special 5-face is incident to exactly one special vertex.

  * If there exist two 5^+-vertices on a 5-face f, then f is neither special nor bad.





 
Every source is a 5^+-vertex.

Let f = [v_1 v_2 v_3 v_4 v_5 v_1] be a small 5-face, and let z be a source of f. By Lemma <ref>, there exists no 3^--vertex in G, thus we suppose that d_G(z)  = 4.
Without loss of generality, we may assume that z is adjacent to v_1 and v_2.
Let G[S] be the subgraph of G induced by S = {z, v_1, v_2, v_3, v_4, v_5 }.
Let L be a list assignment of G with |L(v)|≥ 4 for all v∈ V,
and let _L be a matching assignment over L.
Consider subgraph G' := G - V(G[S]) and L'(v) = L(v) for v ∈ V(G').
By (d),
G' admits an _L'-coloring.
Thus there is an independent set I' in the _L'-cover with |I'| = |V(G)| - |S| = |V(G)| - 6.  For v ∈{v_1, v_2, v_3, v_4, v_5, z }, we define

    L^*(v) = L(v) ∖⋃_uv ∈ E(G){c' ∈ L(v): (u,c)(v,c') ∈ M_L,uv (u, c) ∈ I' }.

Because |L(v)| ≥ 4 for all v ∈ V(G),
we have that |L^*(v_1)| ≥ 3,  |L^*(v_2)| ≥ 3, and |L^*(v)| ≥ 2 for v ∈{v_3, v_4, v_5, z }.
We denote by _L^*
the restriction of _L into G[S] and L^*.

 
The _L^*-cover has an independent set I^* with |I^*| = 6 = |V(G[S])|.

Because d_G(v)=4 for v∈ S, it holds that |L^*(v_1)| ≥ 3 and |L^*(z)| ≥ 2, we can color v_1 by c ∈ L^*(v_1) such that L^*(z) ∖{c' : (v_1, c) (z, c') ∈ M_L^*} has at least two available colors.
By coloring greedily v_5, v_4, v_3, v_2, z in order, we can find an independent set I^* with |I^*| = 6.
This completes the proof of Claim <ref>. 

Thus G admits an _L-coloring I = I' ∪ I^* such that |I| = |I'| + |I^*| = |V(G)|.  It implies that G is DP-4-colorable.  This is contradiction to (c).  Thus d_G(z) ≥ 5.


 Let v be a 5^+-vertex of G. Then the following hold:

(1) v is incident to at most ⌊d(v)/2⌋ 3-faces; and

(2) if v is incident to t 3-faces and 2t<d_G(v), then v is incident to at most t-1 special 5-faces.


Note that (1) holds obviously from (b).

And from the definition of a special 5-face, if v is a 5^+-vertex of G, then each of the special 5-faces incident to v is adjacent to two 3-faces, and both of the two 3-faces are incident to v, which implies (2).



Let v be a 5^+-vertex of G. Assume that v is incident to a special or bad 5-face f_1 and a 3-face f_2 such that f_1 and f_2 are adjacent, then v has no sink adjacent to f_2.





Let f_1=[vv_4v_3v_2v_1v] be a special or a bad 5-face. According to the definition of special 5-face and bad 5-face, there are at least four 3-faces adjacent to f_1. Assume that f_2=[vv_5v_4v], and f_2 is adjacent to f_1 (see Figure <ref>). Suppose to the contrary that v has a sink f_3=[v_4v_5v_6v_7v_8v_4] adjacent to f_2 with a common edge v_4v_5, then v_3 is a source of f_3. However, v_3 is a 4-vertex, contrary to Lemma <ref>.

 Let f_1 and f_2 be two bad 5-faces. Then they can not normally adjacent with one common edge vv_1, where v is the 5^+-vertex on f_1 and f_2.





Assume that two bad 5-faces, say f_1 and f_2, are normally adjacent, and they have one common 5^+-vertex v and one common edge vv_1 (see Figure <ref>). Since
both f_1 and f_2 are bad, then v_1 is a 4-vertex, and f_3=[v_1v_3v_4v_1] and f_4=[v_1v_2v_3v_1] are two 3-faces. Hence f_3 and f_4 are adjacent, contrary to (b). Thus the assumption is false.













 §.§ Discharging


It follows that

    ∑_v∈ V(2d_G(v)-6)+∑_f∈ F(d_G(f)-6)=-12

from Euler's formula |V|-|E|+|F|=2 and the equality ∑_v∈ Vd_G(v)=2|E|=∑_f∈ Fd_G(f).
Now we define an initial charge function ch(x) for each x∈ V∪ F by letting ch(v)=2d_G(v)-6 for each v∈ V and  ch(f)=d_G(f)-6 for each f∈ F. We are going to design several discharging rules. Since the sum of total charge is fixed during the discharging procedure, if we can change the initial charge function ch(x) to the final charge function ch'(x) such that ch'(x)≥0 for each x∈ V∪ F, then

    0≤∑_x∈ V∪ Fch(x)=∑_x∈ V∪ Fch'(x)=-12,

 which is a contradiction. It means that no counterexample to Theorem <ref> exists.  Thus Theorem <ref> holds.



Before designing the discharging rules, we define a configuration as shown in Figure <ref>. In Figure <ref>, the degrees of white vertices are at least the number of edges incident to them, but the degrees of the black vertices are equal to the number of edges incident to them. The red vertex v is a special 5-vertex. In this configuration, f_1 is a special 5-face, f_2 is a bad 5-face, f_3 is a 5-face satisfying the following:

  
  * f_3 is neither special nor bad; and
  
  * f_3 is incident to a special 5-vertex v, and v is incident to a bad 5-face f_2; and
  
  * f_3 is normally adjacent to f_2.

We call F_5 the family of f_3, that is, F_5 is a family of 5-faces that have the same properties of f_3.





Let w be a vertex on f_3 as shown in Figure <ref>. If d_G(w)=4, then w is incident to at most one 3-face according to (b).






Discharging Rules:




  R1 Each 4^+-vertex gives 1 to each incident 3-face.

  R2 Each 4^+-vertex gives 1/2 to each incident 4-face.

  R3 Let v be a 4-vertex incident to at most one 3-face. If v is incident to exactly one 3-face and one 4-face, then v gives 1/4 to each incident 5-face; Otherwise, v gives 1/3 to each incident 5-face.

  R4 By Remark <ref> (1), a special 5-face is exactly incident to one special vertex.
          
          
  R4.1 Each special 5^+-vertex gives 1 to each incident special 5-face.
          

          

          
  R4.2 Each special 5-vertex gives 2/3 to each incident bad 5-face (see f_2 in Figure <ref>).
          
  R4.3 If a special 5-vertex is incident to three 5-faces, which are special 5-face f_1, bad 5-face f_2, and non-special or non-bad 5-face f_3 respectively, then v gives 1/3 to f_3. (See Figure <ref>)
          

  R5 Each non-special 5-vertex and each 6^+-vertex gives 3/4 to each incident bad 5-face.

  R6 Each source gives 1/5 to each of its sinks.

  R7 If u is a 6^+-vertex, or u is a non-special 5-vertex, or u is a special 5-vertex but u is not incident to a bad 5-face, then u gives 1/2 to each incident non-special or non-bad 5-face.   























To complete the proof of Theorem <ref>, it remains to check that the final charge of every element in V∪ F is nonnegative. This will be shown by the following two claims.


It holds that ch'(v)≥0 for all v∈ V(G).


According to Lemma <ref>, there exists no 3^--vertex in G, thus we need to consider the 4^+-vertices in the following.


1: When d_G(v)=4.

In this case, we have that ch(v)=4× 2-6=2. According to Lemma <ref>, v has no any sink.
If v is incident to two 3-faces, then ch'(v)=ch(v)-2× 1=0 by R1.

And, if v is incident to exactly one 3-face, then v is incident to at most one 4-face according to (b). Assume that v is incident to one 4-face, then it is incident to at most two 5-faces. Thus ch'(v)≥ ch(v)-1-1/2-1/4× 2=0 by R1, R2 and R3. Otherwise, v is incident to at most three 5-faces. Therefore, ch'(v)≥ ch(v)-1-1/4× 3>0 by R1 and R3.

If v is not incident to any 3-face, then ch'(v)≥ ch(v)-1/2× 4=0 by R2 and R3.



2: When d_G(v)=5.

In this case, we have that ch(v)=5× 2-6=4.
Assume that v is special, that is, v is incident to a special 5-face by Remark <ref> (1). From Lemma <ref> and the definition of special 5-face, it holds that v is incident to exactly two 3-faces and one special 5-face. According to Lemma <ref>, v has no  sink. If v is incident to a bad 5-face, then v is incident to at most one bad 5-face by Lemma <ref>. We have that ch'(v)≥ ch(v)-1× 2-1-2/3-1/3=0 from R1 and R4. Otherwise v is not incident to any bad 5-face. It holds that ch'(v)≥ ch(v)-1× 2-1-1/2× 2=0 by R1, R4 and R7.

We next assume that v is not special, that is, v is not incident to a special 5-face by Remark <ref> (1). The vertex v is incident to at most two 3-faces by Lemma <ref> (1). According to Lemma <ref>, v is incident to at most two bad 5-faces.

  
  * If v is incident to two 3-faces, then v is incident to at most one bad 5-face from Lemma <ref>, the definition of bad 5-face and (b), and is not incident to any 4-face by (b). Thus we have that ch'(v)≥ ch(v)-1× 2-3/4-1/2× 2>0 from R1, R4 and R7.
  
  * If v is incident to exactly one 3-face, then v is incident to at most two bad 5-faces by the definition of bad 5-face. Thus the final charge ch'(v)> ch(v)-1-1/5-3/4× 2-1/2× 2>0 from R1, R4, R6 and R7.
  
  * If v is not incident to any 3-face, then v is not incident to bad 5-face. It holds that ch'(v)≥ ch(v)-1/2× 5>0 by R2 and R7.



 












3: When d_G(v)=6.

Note that we have that  ch(v)=2× 6-6=6. According to Lemma <ref>, v is incident to at most three 3-faces and at most three special 5-faces.


  
  * Assume that v is incident to three 3-faces. If v is incident to three special 5-faces, then v has no any sink by Lemma <ref>. Thus we have that ch'(v)≥ ch(v)-3-3=0 from R1, R4.1. Otherwise v is incident to at most two special 5-faces. Then v has no any sink by Lemma <ref>.
  Hence we have that
ch'(v)≥ ch(v)-3 - 2-3/4>0

from R1, R4.1 and R5.
  
  * Assume that v is incident to at most two 3-faces, then v is incident to at most one special 5-faces by Lemma <ref> (2).
      If v is incident to one special 5-faces, then ch'(v)> ch(v)-2(1+1/5)-1-3/4×3>0 from R1, R4.1, R5 and R6. Otherwise,
      by Lemma <ref>, v is incident to at most two bad 5-faces. Therefore, it holds that ch'(v)> ch(v)-2(1+1/5)-3/4×2-1/2× 2>0 from R1, R4.1, R5, R6 and R7.


4: When d_G(v)= 7.

In this case, we have that ch(v)=2× 7-6=8. By Lemma <ref>, v is incident to at most three 3-faces and at most two special 5-faces. The smallest final charge ch'(v)> ch(v)-3(1+1/5)-2-3/4×2>0 from R1, R4.1, R5 and R6.


5: When d_G(v)= k≥8.

Observe that ch(v)=2k-6. By Lemma <ref>, v is incident to at most ⌊d_G(v)/2⌋ 3-faces and at most ⌊d_G(v)/2⌋ special 5-faces.
It holds that ch'(v)≥ ch(v)-(1+1/5)×⌊d_G(v)/2⌋-1×⌈d_G(v)/2⌉>0 by R1, R4.1 and R6.






It holds that ch'(f)≥0 for all f∈ F(G).


Let f be a face of G. Because G is simple, G has no loops and multi-edges. Thus d_G(f)≥3. If d_G(f)≥ 6, no charge is discharged from or to f, thus ch'(f)=ch(f)=d_G(f)-6≥0.
If d_G(f)=3, then every vertex incident to f gives 1 to f according to R1. Therefore, we have that ch'(f)=ch(f)+3× 1=d_G(f)-6+3=0. If d_G(f)=4, then every vertex incident to f gives 1/2 to f according to R2. Hence the final charge ch'(f)=ch(f)+4×1/2=d_G(f)-6+2=0. Next we assume that d_G(f)=5. Note that ch(f)=5-6=-1.



1: Assume that f is small, that is, all the vertices incident to f are 4-vertices.

For 0 ≤ t ≤ 5, let t be the number of 4-vertices which are incident to two 3-faces.  Then f has (5 - t) 4-vertices which are incident to at most one 3-face, and f has at least t+1 sources.  Thus we have
ch'(f)≥ -1+ 1/4× (5 - t) +1/5× (t+1) = 9 - t/20 >0
for every t ∈{0, 1, 2, 3, 4, 5 } by R3 and R6.











2: When f is a (5^+,4,4,4,4)-face.

Denote the 5^+-vertex by v. If f is special, then ch'(f)≥ -1+1=0 according to R4.1. Next let f be a non-special 5-face.

  
  * Assume that v is a special 5-vertex and v is incident to a bad
  5-face (see Figure <ref>). If f is bad, then ch'(f)≥ -1+2/3+1/3=0 according to R4.2 and R3. Otherwise f is not bad, then f ∈ F_5. Hence f is incident to at least two 4-vertices which are incident to at most one 3-face, and are not incident to a 3-face and a 4-face at the same time by Remark <ref>, respectively. Therefore, we have that ch'(f)≥ -1+1/3×2+1/3=0 according to R3, R4.3 and R7.

  
  * Otherwise, v is a 6^+-vertex, or v is not a special 5-vertex, or v is a special 5-vertex and v is not incident to a bad 5-face. If f is bad, then there exists a 4-vertex incident to f, and the 4-vertex is incident to at most one 3-face. Thus we have that ch'(f)≥ -1+1/4+3/4=0 according to R3 and R5. Otherwise f is not bad. Hence there are at least two 4^+-vertices incident to f, and each of them is incident to at most one 3-face. We can conclude that ch'(f)≥ -1+1/4×2+1/2=0 according to R3 and R7.




3: When there exist at least two 5^+-vertices on f.

From Remark <ref> (2), we have that f is neither special nor bad.

  
  * If f ∈  F_5, then ch'(f)≥ -1+1/3×2+1/3=0 by R3, R4.3 and R7.
  
  * Otherwise f∉ F_5, that is, f is not incident to a special 5-vertex which is on a special 5-face and is incident to a bad 5-face. We can conclude that ch'(f)≥ -1+1/2×2=0 according to R7. 


The proof of Theorem <ref> is completed.






§ REMARKS







 §.§ Difference between DP-coloring and list coloring


A θ-graph is a graph consisting of two 3-vertices and three pairwise internally disjoint paths between the two 3-vertices. A θ-subgraph of G is an induced subgraph that is isomorphic to a θ-graph. We use Sθ to denote such a special θ-subgraph of G in which one of the ends of the internal chord is a 5^--vertex and all of the other vertices are 4-vertices in G.





Let G be a planar graph without 4-cycles adjacent to 3-cycles. In the proof of Theorem <ref> (A), the authors showed that if G is not 4-choosable with fewest vertices, then G contains no subgraph isomorphic to Sθ (see Lemma 4 in <cit.>). But we can not claim that if G is not DP-4-colorable with fewest vertices, then G contains no subgraph isomorphic to Sθ. Next we give an explanation.













In Figure <ref> (a), assume that d_G(v_1) = 5, d_G(v_i) = 4 for i ∈{2, 3, 4, 5} and d_G(z) = 4.
Let G[S] be the subgraph of G induced by S = {z, v_1, v_2, v_3, v_4, v_5 }.
Let L be a list assignment of G with |L(v)|≥ 4 for all v∈ V,
and let _L be a matching assignment over L.
Set G' := G - S and L'(v) = L(v) for v ∈ V(G').
By (d), G' admits an _L'-coloring.
Thus there is an independent set I' in the _L'-cover with |I'| = |V(G)| - |S| = |V(G)| - 6.  For v ∈{v_1, v_2, v_3, v_4, v_5, z }, we define

    L^*(v) = L(v) ∖⋃_uv ∈ E(G){c' ∈ L(v): (u,c)(v,c') ∈ M_L,uv (u, c) ∈ I' }.

Because |L(v)| ≥ 4 for all v ∈ V(G),
we have that |L^*(v_5)| ≥ 3, and |L^*(v)| ≥ 2 for v ∈{z,v_1,v_2, v_3, v_4}.
We denote by _L^*
the restriction of _L into G[S] and L^*.



Next we give a _L^*-cover as shown in (b) of Figure <ref>. But we cannot find an independent set I^* with |I^*| = 6 in _L^*-cover. Thus we cannot claim that if G is not DP-4-colorable with fewest vertices, then G contains no subgraph isomorphic to Sθ. Therefore, Theorem <ref> is not trivial from Theorem <ref> (A).









 §.§ Relationship with signed coloring

There is a concept of signed coloring of signed graphs, which
was first defined by Zaslavsky <cit.>
with slightly different form,
and then modified by Máčajová, Raspaud, and Škoviera <cit.>
so that it would be a natural extension of an ordinary vertex
coloring.  For detail story about signed coloring, we refer readers to <cit.>.

An interesting obervation in <cit.> is that the signed coloring of a signed graph (G,σ)
is a special case of a DP-coloring of G.  Thus Theorem <ref> implies the following corollary, which is an extension of the result in <cit.>.


A graph G is signed 4-choosable if G is a planar graph without 4-cycle adjacent to a 3-cycle.




99





Alon N. Alon. Degrees and choice numbers.
Random Structures & Algorithms 16 (2000), 364–368.

Bernshteyn A. Bernshteyn. The asymptotic behavior of the correspondence chromatic number.
Discrete Math. 339 (2016), 2680–2692.


BK2 A. Bernshteyn, A. Kostochka.
On differences between DP-coloring and list coloring.
arXiv:1705.04883, (2017), preprint.


BKP A. Bernshteyn, A. Kostochka, S. Pron.
On DP-coloring of graphs and multigraphs.
Sib. Math.l J. 58 (2017), 28–36.


BKZ A. Bernshteyn, A. Kostochka, X. Zhu.
DP-colorings of graphs with high chromatic number.
European J. Combin. 65 (2017), 122–129.

CCW P. Cheng, M. Chen, Y. Wang. Planar graphs without 4-cycles adjacent to triangles are 4-choosable. Discrete Math. 339 (12) (2016), 3052–3057.

DP Z. Dvořák, L. Postle.
Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8.


J. Comb. Theory, Ser. B., (2017), In press.

ERT P. Erdos, A.L.Rubin, H.Taylor. Choosability in graphs. Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium XXVI (1979), 125-157.

JKS L. Jin, Y. Kang, E. Steffen.
Choosability in signed planar graphs.
Europ. J. Combin. 52 (2016), 234–243.


KO S.-J. Kim, K. Ozeki.
A note on a Brooks' type theorem for DP-coloring.
arXiv:1709.09807, (2017), preprint.


KO2 S.-J. Kim, K. Ozeki.
A Sufficient condition for DP-4-colorability.
arXiv:1709.09809, (2017), preprint.


Lam
P. C.-B. Lam, B. Xu, J. Liu.
The 4-Choosability of Plane Graphs without 4-Cycles. J. Comb. Theory, Ser. B 76(1) (1999), 117–126.

MRS E. Máčajová, A. Raspaud, M. Škoviera.
The chromatic number of a signed graph.
the Electron. J Combin. 23 (2016), #P1.14.





Thomassen C. Thomassen. Every Planar Graph Is 5-Choosable. J. Comb. Theory, Ser. B. 62(1) (1994), 180–181.

Vizing V.G.Vizing. Vertex colorings with given colors (in Russian). Diskret. Analiz., 29 (1976): 3-10.


Voigt M. Voigt.
A not 3-choosable planar graph without 3-cycles. Discrete Math. 146 (1995), 325–328.






Zaslavsky T. Zaslavsky.
Signed graph coloring.
Discrete Math. 39 (1982), 215–228.















