3 Acyclic improper colorings of planar graphs

Negative results on acyclic improper colorings

Pascal Ochem

1LaBRI, Universit´e Bordeaux I

351, cours de la Lib´eration, 33405 Talence Cedex, FRANCE [email protected]

Raspaud and Sopena showed that the oriented chromatic number of a graph with acyclic chromatic numberk is at mostk2^k−1. We prove that this bound is tight fork ≥ 3. We also show that some improper and/or acyclic colorings are NP-complete on a classCof planar graphs. We try to get the most restrictive conditions on the classC, such as having large girth and small maximum degree. In particular, we obtain the NP-completeness of 3-ACYCLIC COLORABILITYon bipartite planar graphs with maximum degree 4, and of 4-ACYCLIC COLORABILITYon bipartite planar graphs with maximum degree 8.

Keywords:acyclic colorings, oriented colorings, NP-completeness

1 Introduction

Oriented graphs are directed graphs without opposite arcs. In other words an oriented graph is an orien- tation of an undirected graph, obtained by assigning to every edge one of the two possible orientations.

IfGis a graph,V(G)denotes its vertex set, E(G)denotes its set of edges (or arcs ifGis an oriented graph). A homomorphism from an oriented graphGto an oriented graphH is a mappingϕfromV(G) toV(H)which preserves the arcs, that is(x, y)∈E(G) =⇒(ϕ(x), ϕ(y))∈E(H). We say thatHis a target graphofGif there exists a homomorphism fromGtoH. The oriented chromatic numberχo(G) of an oriented graphGis defined as the minimum order of a target graph ofG. The oriented chromatic numberχo(G)of an undirected graphGis then defined as the maximum oriented chromatic number of its orientations. Finally, the oriented chromatic numberχo(C)of a graph classCis the maximum ofχo(G) taken over every graphG∈ C. We use in this paper the following notations:

Pkdenotes the class of planar graphs with girth at leastk.

oc(k)denotes the class of graphs with oriented chromatic number at mostk.

Skdenotes the class of graphs with maximum degree at mostk.

Tk denotes the class of partialk-trees.

Dkdenotes the class ofk-degenerate graphs.

bipdenotes the class of bipartite graphs.

†Research supported in part by COMBSTRU.

1365–8050 c2005 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

A vertex coloringcof a graphGisacyclicif for every two distinct colorsiandj, the edgesuvsuch thatc(u) =iandc(v) =jinduce a forest. The acyclic chromatic numberχ_a(G)is the minimum number of colors needed in an acyclic proper coloring of the graphG. Similarly, the acyclic chromatic number χa(C)of a graph classCis the maximum ofχa(G)taken over every graphG∈ C. Raspaud and Sopena showed in [12] that:

Proposition 1 [12] For every graphGsuch thatχa(G) =k,χo(G)≤k2^k−1.

Together with the result of Borodin that planar graphs are acyclically 5-colorable (i.e.χ_a(P₃) = 5), this implies that the oriented chromatic number of a planar graph is at most 80 (i.e. χo(P3)≤80), which is yet the best known upper bound. See [3, 11] for the known upper bounds onχo(Pn)forn≥4. In order to get a better upper bound onχo(P3), if possible, it is interesting to study the tightness of Proposition 1, in particular fork= 5. The previously best known lower bound on the maximum value ofχo(G)in terms of χa(G)was given in [16] with a family of graphsGk,k≥1such thatχa(Gk) =kandχo(Gk) = 2^k−1.

The notion of acyclic improper coloring was introduced in [1]. LetC0, . . . ,Ck−1be graph classes. A graphGbelongs to the classC0 · · · Ck−1if and only ifGhas an acyclick-coloring such that thei^th color class induces a graph inC_i, for0≤i≤k−1. The main motivation in the study of acyclic improper colorings is the following generalization of Proposition 1.

Proposition 2 [1] LetC0, . . . ,C_k−1be graph classes such thatχo(Ci) =ni, for0≤i < k. Every graph G∈ C0 · · · C_k−1satisfiesχo(G)≤2^k−1Pi<k

i=0ni.

The bound of Proposition 2 is shown to be tight fork≥3under mild assumptions in Section 2.

We know from [13, 15] thatχo(T3) =χo(T3∩ P3) = 16. Thus, Boiron et al. [1] point out that:

1. P3⊂ T3 S0 S0would imply thatχ_o(P3)≤72, 2. P3⊂ T3 S1 S0would imply thatχo(P3)≤76.

We will see that the second point is meaningless. Indeed, we have thatP₃ ⊂ T₃ S₁ S₀ ⇐⇒ P₃ ⊂ T3 S0 S0from a general result on acyclic improper colorings of planar graphs given in Section 3.

In Section 4, we prove the NP-completeness of five coloring problems where the input graph is planar with some large girth and low maximum degree.^‡.

2 Acyclic improper coloring versus oriented coloring

Theorem 1 Letk ≥3. LetC0, . . . ,Ck−1be hereditary graph classes closed under disjoint union, and such thatχo(Ci) =ni. Thenχo(C0 · · · C_k−1) = 2^k−1Pi<k

i=0ni.

Proof: We construct an oriented graph G ∈ C0 · · · Ck−1 such thatχ_o(G) = 2^k−1Pi<k i=0n_i. Let u₁, u₂, u₃ be a directed 2-path with arcsu₁u₂ andu₂u₃, or u₃u₂ andu₂u₁. We say thatu₁ andu₃ are theendpointsof the directed 2-path. By definition, the endpoints of the directed 2-path get distinct colors in any oriented coloring. Sinceχ_o(C_i) = n_i, there exists a witness oriented graphWⁱsuch that χo(Wⁱ) =ni. The graphGicontainsk−1independent verticesvⁱ_j, 0≤j < k−1and2^k−1disjoint

‡A full paper version of this extended abstract containing all proofs is available at:

http://dept-info.labri.fr/˜ochem/acyclic.ps

copiesW_lⁱ, 0≤l <2^k−1ofWⁱ. We consider the binary representationl=Pn<k−1

n=0 2ⁿx_n(l)ofl. For every two verticesvⁱ_janduⁱ_l ∈ W_lⁱ, we put the arcv_jⁱuⁱ_l (resp. uⁱ_lvⁱ_j) ifx_j(l) = 1(resp. x_j(l) = 0). If l 6=l⁰, their binary representations differ at then^thdigit, thusuⁱ_l ∈W_lⁱuⁱ_l0 ∈W_lⁱ0are the endpoints of a directed 2-pathuⁱ_l, v_nⁱ, uⁱ_l0. So the same color cannot be used in distinct copies ofWⁱ, which means that at least2^k−1n_icolors are needed to color the copies ofWⁱin any oriented coloring ofG_i. We acyclically colorG_ias follows. Thek−1verticesv_jⁱget pairwise distinct colors in{0, . . . , k−1} \ {i}and every vertexuⁱ_lget colori(that is why we need the ”closed under disjoint union” assumption). LetSi denote the set of colors in some oriented coloring of the verticesuⁱ_lofGi. Now we take one copy of each graph Giand finish the construction ofG. For every two verticesuⁱ_l ∈ W_lⁱ anduⁱ_l0⁰ ∈ W_lⁱ0⁰, such thati 6= i⁰, we add a new vertexland create a directed 2-pathuⁱ_l, l, uⁱ_l⁰0. So, fori6=i⁰, we haveSi∩Si⁰ =∅, which means that at least2^k−1Pi<k

i=0ni colors are needed in any oriented coloring ofG. To obtain an acyclic coloring ofG, the new vertexladjacent touⁱ_landuⁱ_l0⁰ gets a color in{0, . . . , k−1} \ {i, i⁰}, which is

non-empty ifk≥3. 2

Notice that Theorem 1 cannot be extended to the case k = 2 in general. By settingk = 2 and C₀=C₁=S₀, we obtain the class of forestsS₀⁽²⁾=D₁. Proposition 2 provides the boundχ_o(S₀⁽²⁾)≤4.

This is not a tight bound, since oriented forests have a homomorphism to the oriented triangle, and thus χo(S₀⁽²⁾) = 3.

The proof of Theorem 1 is constructive, but it does not help for the problem of determiningχo(P3).

Indeed, the graph corresponding to the proper 5-acyclic coloring (i.e.k= 5andC0=· · ·=C4=S0) is highly non-planar (it contains e.g.K_32,48as a minor).

3 Acyclic improper colorings of planar graphs

Theorem 2 Let2≤k≤4.

ThenP₃⊂ C₀ · · · C_k−2oc(14)⇐⇒ P₃⊂ C₀ · · · C_k−2S₀.

Theorem 2 allows us to study which statement of the form “every planar graph belongs toC₀· · ·C_k−1” may improve the upper boundχ_o(P₃)≤80. Ifk= 4, the ”least” candidate class would beoc(15)S₀ S₀S₀, but the corresponding bound is too large (2⁴⁻¹(15 + 1 + 1 + 1) = 144>80). Ifk= 1, there must be exactly one improper color, otherwise the least candidateoc(15)oc(15)S0provides a too large bound (2³⁻¹(15 + 15 + 1) = 124>80).

The constant 14 in Theorem 2 can be improved to 15 using ideas in [15].

We have not been able to get similar results for planar graphs with larger girth.

4 NP-complete colorings

A graphGbelongs to the classC0◦ · · · ◦ C_k−1if and only ifGhas ak-coloring such that thei^thcolor class induces a graph inCi, for0≤i≤k−1. For brevity, ifC0=· · ·=C_k−1=Cwe will denote byC^k the classC0◦ · · · ◦ Ck−1and byC^(k)the classC0 · · · Ck−1. IfC1andC2are graph classes, we note (C1:C2)the problem of deciding whether a given graphG∈ C1belongs toC2. IfP1andP2are decision problems, we noteP1∝P2if there is a polynomial reduction fromP1toP2.

Kratochvil proved thatPLANAR(3,^≤4)-SATis NP-complete [9]. In this restricted version ofSAT, the graph of incidences variable-clause of the input formula must be planar, every clause is a disjonction of

exactly three literals, and every variable occurs in at most four clauses. A subcoloring is a partition the vertex set into disjoint cliques. The problem 2-SUBCOLORABILITYis NP-complete on triangle-free pla- nar graphs with maximum degree 4 [5, 7]. Notice that on triangle-free graphs, a 2-subcoloring correspond to a vertex partition into two graphs with maximum degree 1. Finally, the problem 3-COLORABILITYis shown to be NP-complete on planar graphs with maximum degree 4 in [6].

Theorem 3 PLANAR(3,^≤4)-SAT∝(P6∩ S3:S0◦ S1)

Notice that on triangle-free graphs, theS0◦ S1 coloring correspond to the(1,2)-subcoloring defined in [10]. Theorem 3 improves a result in [10] stating that(P4∩ S3:S0◦ S1)is NP-complete.

Theorem 4 PLANAR(3,^≤4)-SAT∝(P₁₀∩ S₃∩bip:S₀ S₁) Theorem 5 (P4∩ S4:S₁²)∝(P8∩ S4∩bip:S₁⁽²⁾)

Theorem 6 (P₃∩ S₄:S₀³)∝(P₄∩ S₄∩bip∩ D₂:S₀⁽³⁾)

2 1 3

3

2 1

1 2 3

1 1

2 3

1 3 2

3 2

2 1 3

3

2 1

1 2 3

1 1 2 3

1 3 2

3 2

2 1 3

3

2 1

1 2 3

1 1 2 3

1 3 2

3 2

2 1

u2 u3 u4 u5 u6 u7

u1

etc..

Figure 1:The vertex gadget for the reduction of Theorem 6.

Given a planar graphG, we construct the graphG⁰ as follows. We replace every vertexvofGby a copy of the vertex gadget depicted in Figure 1 and for every edgevwwe link a big vertexui in the gadget of vto a small vertexu_iin the gadget ofw. The given 3-acyclic coloring of the vertex gadget is the unique one up to permutation of colors. Notice that allu_iget the same color and there exists no alternating path between distinctu_i. This common color in the gadget of a vertexv correspond to the color ofv in a 3-coloring ofG. ThusG⁰is acyclically 3-colorable if and only ifGis 3-colorable.

Theorem 7 (P3∩ S4:S₀³)∝(P4∩ S8∩bip∩ D2:S₀⁽⁴⁾)

References

[1] P. Boiron, E. Sopena and L. Vignal. Acyclic improper colourings of graphs, J. Graph Theory32 (1999), 97–107.

[2] O.V. Borodin. On acyclic colorings of planar graphs,Discrete Math.25(1979), 211–236.

[3] O.V. Borodin, A.V. Kostochka, J. Neˇsetˇril, A. Raspaud and E. Sopena. On the maximum average degree and the oriented chromatic number of a graph,Discrete Math.206(1999), 77–89.

[4] O.V. Borodin, A.V. Kostochka and D.R. Woodall. Acyclic colorings of planar graphs with large girth,J. London Math. Soc.60(1999), 344–352.

[5] J. Fiala, K. Jansen, V.B. Le and E. Seidel. Graph Subcolorings: Complexity and Algorithm,SIAM J.

Discrete Math.16(4)(2003), 635–650.

[6] M.R. Garey, D.S. Johnson and L.J. Stockmeyer. Some simplified NP-Complete graph problems, Theor. Comput. Sci.1(3)(1976), 237–267.

[7] J. Gimbel and C. Hartman. Subcolorings and the subchromatic number of a graph,Discrete Math.

272(2003), 139–154.

[8] A.V. Kostochka and L.S. Mel’nikov. Note to the paper of Gr¨unbaum on acyclic colorings,Discrete Math.14(1976), 403–406.

[9] J. Kratochvil. A Special Planar Satisfiability Problem and a Consequence of its NP-Completeness, Discrete Appl. Math.52(1994), 233-252.

[10] H. Le and V.B. Le. The NP-completeness of(1, r)-subcolorability of cubic graphs,Inform. Process.

Lett.81(3)(2002), 157–162.

[11] P. Ochem. Oriented colorings of triangle-free planar graphs,Inform. Process. Lett.92(2) (2004), 71–76.

[12] A. Raspaud and E. Sopena. Good and semi-strong colorings of oriented planar graphs,Inform. Pro- cess. Lett.51(1994), no.4, 171–174.

[13] E. Sopena. The chromatic number of oriented graphs,J. Graph Theory25(1997), 191–205.

[14] E. Sopena. Oriented graph coloring,Discrete Math.229(1-3)(2001), 359–369.

[15] E. Sopena. There exist oriented planar graphs with oriented chromatic number at least sixteen,In- form. Process. Lett.81(6)(2002), 309–312.

[16] L. Vignal. Homomorphismes et colorations de graphes orient´es, Ph.D. Thesis, LaBRI, Universit´e Bordeaux I (1997).