Density of universal classes of series-parallel graphs

Density of universal classes of series-parallel graphs

Jaroslav Neˇsetˇril

and Yared Nigussie

1Department of Applied Mathematics Institute for Theoretical Computer Science(ITI) Charles University

Malostransk´e n´am.25

11800 Praha 1 Czech Republic

A class of graphsC ordered by the homomorphism relation isuniversalif every countable partial order can be embedded inC. It was shown in [1] that the classCkofk-colorable graphs, for any fixedk≥3, induces a universal partial order. In [4], a surprisingly small subclass ofC3which is a proper subclass ofK4-minor-free graphs (G/K4) is shown to be universal. In another direction, a density result was given in [9], that for each rational numbera/b∈ [2,8/3]∪ {3}, there is aK4-minor-free graph with circular chromatic number equal toa/b. In this note we show for each rational numbera/bwithin this interval the classKa/bofK4-minor-free graphs with circular chromatic number a/bis universal if and only ifa/b 6= 2, 5/2 or 3. This shows yet another surprising richness of theK4-minor-free class that it contains universal classes as dense as the rational numbers.

Keywords:circular chromatic number, homomorphism, series-parallel graphs, universality

1 Introduction

We assume graphs are finite and simple (with no loops and parallel edges). Let G, G⁰ be graphs. A homomorphism from Gto G⁰ is a mappingf:V(G) → V(G⁰) which preserves adjacency. That is, {u, v} ∈ E(G)implies{f(u), f(v)} ∈ E(G⁰). We writeG ≤G⁰ if there is a homomorphism fromG toG⁰. The notationG < G⁰meansG≤G⁰ 6≤ G, whereasG∼G⁰ meansG≤ G⁰ ≤G. IfG∼G⁰, we sayGandG⁰ arehom-equivalent. The smallest graphH for whichG∼ H is called thecoreofG.

For finite graphs, the core is uniquely determined up to an isomorphism. It can also be seen thatHis an induced subgraph ofG. This will be denoted byH ⊆G. LetCandC⁰be two classes of graphs. We also writeC ∼ C⁰if for each graphG∈ Cthere exists aG⁰ ∈ C⁰such thatG∼G⁰and vice versa. See [2] for introduction to graphs and their homomorphisms.

Letk≥d≥1be integers. Thecircular chromatic numberofG, writtenχc(G), is the smallest rational k/dsuch thatG ≤K_k/d, whereK_k/d is thecircular graphwithV(K_k/d) = {0,1,2, . . . , k−1}and

†Supported by a Grant 1M0021620808 of Czech Ministry of Education

‡Partially supported by DIMATIA and 1M0021620808

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

Pe1 Pe2

Pe3 Pe4

G’

x y z

Fig. 1:Unavoidable configuration ofG(a minimal counterexample to Lemma 6) with odd girth2k+1andle₁+le₂ = le₃+le₄ = 2k+ 1.

E(K_k/d) ={{i, j}:d≤ |i−j| ≤k−d}. Note that whend= 1we have the usual vertex coloring of G. LetK_a/b{G∈ G/K₄ :χ_c(G) =a/b}. See [10] for some other equivalent definitions. It is trivial to see the following:

Theorem 1 K2∼ {K2}.

It is well known that graphs inG/K₄are 3-colorable. Hell and Zhu [3] have shown that triangle-free graphs in G/K4 have circular chromatic number at most 8/3. Hence no graph in G/K4 has circular chromatic number in the interval (8/3,3). Hence, we have:

Theorem 2 K₃∼ {C₃}.

The main results of this note are the following two theorems establishing nice dichotomy between univer- sality and homomorphism finiteness of the classK_a/b:

Theorem 3 K_5/2∼ {C₅}.

Somewhat surprisingly we show that Theorem 1, 2, and 3 cover all cases whenK_a/bis a finite set.

Theorem 4 K_a/bis universal ifa/b∈(2,5/2)∪(5/2,8/3].

In section 2 we prove Theorem 3 using a folding lemma. In section 3 we prove Theorem 4.

2 K

is equivalent to {C

}

LetGbe a graph. AthreadinGis a pathP ⊆Gsuch that the two endpoints ofPhave degree at least 3 and all internal vertices ofP are degree 2 inG. We shall often use the fact that ifP andP⁰are two edge-disjoint paths and if the lengths ofPandP⁰have same parity such thatPis a thread and has at least equal length asP⁰, then there is a homomorphism that mapsP toP⁰ sending the two ends ofP to the two ends ofP⁰. Such a homomorphism is said tofoldP toP⁰. LetGbe a graph and letG^sdenote the multi-graph we obtain fromGby “smoothing” all degree 2 vertices ofG. For each edgeeofG^s, letP_e denote the thread ofGrepresented byeinG^s, and letl_edenote the length ofP_e.

The following Folding Lemma forK4-minor-free graphs is an analogy of the Folding Lemma of Kloster- meyer and Zhang [6] for planar graphs. Its proof is easy (see [7]).

Lemma 5 (Edge folding lemma) LetG∈ G/{K₄}be of odd girth2k+ 1and lete, e⁰be parallel edges inG^s, with common end verticesx, y. IfGis not homomorphic to a strictly smaller graph of the same odd girth, thenl_e+l_e⁰ = 2k+ 1. Moreover,P_e∪P_e⁰is the unique cycle of length2k+ 1containing both xandy.

For short letK^mdenoteK(7+5m)/(3+2m). Recall thatV(K^m) ={0,1, . . . ,6 + 5m}.

Lemma 6 LetG∈ G/{K4}be of odd girth at least 7. Thenχ_c(G)≤(7 + 5m)/(3 + 2m)<5/2, for somem <|V(G)|/2.

Proof: LetG∈ G/{K4}be a core of odd girthg ≥7. It suffices to showG≤K^mfor somem≥0.

LetG¯^sbe the graph we get by identifying parallel edges ofG^s. Then,G¯^s∈ G/K₄and so there exists a y∈V( ¯G^s)such that the degreedegG¯^s(y) = 2. Then3≤deg_Gs(y)≤4(here we use a parity argument that, the multiplicity of edges ofG^s is at most two, asGis a core). By Lemma 5, and assumingGis a minimal counterexample we can getdegG^s(y) = 4. Hence, a configuration depicted in Figure 1 is unavoidable. LetG⁰ =G−(S4

i=1Pe_i − {x, z}). By inductionG⁰ ≤K^m, for somem ≥0. We can assumef(x) = 0. By investigating a few cases for values of f(y), it is not hard to seeG ≤ K^m+1, contrary to assumption (see [7] for detailed proof). 2Proof of Theorem 3:LetG∈ K5/2be of odd girthg. ThenG≤C₅. By Lemma 6, we haveg≤5. By Theorem 2,g >3. Henceg= 5and so C₅≤G≤C₅. HenceG∼C₅. The converse is obvious sinceχ_c(C₅) = 5/2.

3 Universal sets of G/K

are dense in (2, 5/2) ∪ (5/2, 8/3]

In this section we shall show that we obtain a universal classKp/q⊂ G/K4for arbitraryp/q∈(2,5/2)∪ (5/2,8/3]. We use a graphG_p/qwithχ_c(G) = p/qas a generator ofK_p/q. We assumeG_p/q has the following two properties:

(P1)G_p/qis hom-equivalent neither to a cycle nor to a vertex.

(P2)ifG⁰∈ G/K4satisfies (P1) andχc(G⁰) =p/q, then|V(G⁰)| ≥ |V(G)|.

Lemma 7 LetG∈ G/K4have properties (P1) and (P2). Then,Gis 2-connected. Moreover,Gis a core and it is not vertex-transitive.

Proof: Since the circular graph K_k/d is a vertex-transitive graph, for all k, d, we have χ_c(G) = maxi(χc(Hi)),1 ≤ i ≤ p, where eachHi is a 2-connected component ofG. Here, (P2) implies that p= 1and soGis 2-connected. Next, note that any graphG ∈ G/K4is vertex-transitive if and only if Gis an odd cycle orK1orK2. This is because all other 2-connected graphs inG/K4have at least one degree-2 vertex and one non-degree-2 vertex. Hence by (P1),Gis not vertex-transitive. Moreover, by (P1) the core ofGalso is not vertex-transitive. By (P2), we deduceGis a core. 2For any rational numberp/q∈(2,8/3], Pan and Zhu have shown in [9] a recursive method of constructing a 2-connected graphG_p/qwithχc(G) =p/q. Ifp/q6= (2k+ 1)/kthenG_p/qsatisfies (P1). Ifp/q= (2k+ 1)/k, the graph given in [9] is the cycleC2k+1which is the natural candidate. Cycles do not satisfy (P1), hence we introduce a graph denoted byG^kof odd girth2k+ 3as follows: Take a triangle and double each edge to obtain a multi-graphH. Fori= 0,1,2, let{eⁱ₁, eⁱ₂}, be the three parallel pairs of edges ofH. To obtain a thread of lengthk+ 2, subdividee⁰₁ande¹₁eachk+ 1times. Next subdividee⁰₂ande¹₂eachktimes.

Finally, subdividee³₁three times ande³₂,2k−2times to obtain the graphG^k. We have:

Lemma 8 χ_c(G^k) = (2k+ 1)/kfor allk≥3.

Proof: It is easy to see thatG^k ≤ C2k+1, andG^k 6≤ C2k+3. Hence, we have(2k+ 3)/(k+ 1) <

χc(G^k)≤(2k+ 1)/k. Note thatgcd(4k+ 4,2k+ 1) = 1. From basic number theory [8], using what is known as theFarey sequence, we can see that any rational strictly between(2k+3)/(k+1)and(2k+1)/k

has numeratora≥4k+ 4. But then, ifk≥3the circumference ofG^k is4k+ 3. It is well known [10]

that the numeratoraof a circular chromatic numbera/bof a graphGis at most its circumference. We

deduceχ_c(G^k) = (2k+ 1)/k. 2

Corollary 9 For every rational numberp/q∈(2,5/2)∪(5/2,8/3]there is a graphGp/qsatisfying (P1) and (P2).

Next we prove thatKp/qinherits universality from the classPof directed finite paths [5]. We take several isomorphic copiesH₁, . . . , H_n of a fixed graphH, such thatχ_c(H) = p/qand construct a ‘path-like’

structured graphH⁰by identifying a vertex ofH_iwith a vertex ofH_i+1. Thenχ_c(H⁰) =χ_c(H)because the circular graphs are vertex-transitive. We call such a constructionK₁-concatenation. A more precise definition of ‘K₁-concatenation’ of a graphH:

LetP ∈ P be an oriented path of length n ≥ 1,V(P) = {v1, v2, . . . , vn+1}. Then either vivi+1 or vi+1vi ∈E(P)(but not both). LetH be a graph anda, b∈V(H). LetH1, H2, . . . , Hnbe isomorphic copies ofH and letai, bi be the vertices ofHi corresponding toaandb. TheK1-concatenationofH byP is a graphP ∗(H, a, b)constructed as follows: Fori = 1, . . . , n, if vivi+1 ∈ E(P), choosebi

(otherwise chooseai). Then identify every chosen vertex ofHiwith the unchosen vertex ofHi+1. To make the construction non-trivial, we chooseaandbso that there is no automorphism sendingatoborb toa. IfH satisfies (P1), then we know there exists such a pair.

Lemma 10 LetG_p/q∈ G/K4satisfy(P1),(P2). Then,Kp/qis universal.

Proof:Since the class of oriented pathsPis universal we show for everyP, P⁰∈ P, we haveP ≤P⁰if and only ifP∗(G_p/q, a, b)≤P⁰∗(G_p/q, a, b). This proves the lemma.

The forward implication is straightforward. To prove the reverse implication, letP, P⁰ ∈ P of length nandn⁰ such thatP is a core and suppose there exists a homomorphismf : P∗(G_p/q, a, b)→ P⁰∗ (G_p/q, a, b). Assume further thatPis not an edge, since this case is trivial, and without loss of generality, assume that the first edge ofP is directed forward. Let H1, . . . , Hn andH₁⁰, . . . , H_n⁰0 be isomorphic copies ofG_p/q. First we show thatf|H_i is induced by an automorphism ofG_p/qfor eachi. Suppose not.

Then the imagef(Hi)is connected. Iff(Hi)is 2-connected then, it is isomorphic toG_p/q, sinceG_p/q is a core. Supposef(Hi)is not 2-connected. Then each 2-connected componentFoff(Hi)is a proper subgraph ofG_p/q. By (P2), we haveχc(F)< p/q. Then,H 6≤f(Hi), a contradiction. Hencef|H_i is induced by an automorphism ofG_p/q.

Now we claim a stronger assertion that for anyi,f(a_i) =a⁰_j andf(b_i) = b⁰_j, for somej,1 ≤j ≤m.

letH_j⁰ =f(H₁). Sincef|_H1is an automorphism,f(b₁)must be in the same automorphism class ofb⁰_j. Suppose thatf(b₁) 6= b⁰_j, thenf(b₁)is not a cut-vertex ofP⁰∗(G_p/q, a, b). As b₁ is a cut-vertex of P ∗(G_p/q, a, b), it is identified with eithera2 orb2. If it were identified witha2, thenf|H₂ would be an automorphism ofG_p/qsuch thatf(a2) =b⁰_j, contrary to the choice ofa, binV(G_p/q). Henceb1is identified withb2. Similarly, we geta2is identified witha3, andb3withb4and so on. This impliesP is a ‘zig-zag’ which is hom-equivalent to an edge, contrary toP being a core. Sof(b1) = b⁰_j. The claim follows by induction on the length ofP.

We define a homomorphismg :V(P)→V(P⁰)so that iff(a_i) =a⁰_j theng(v_i) =v_j⁰ and similarly for b_i. By our constructiongpreserves the adjacency condition and soP ≤P⁰. 2Proof of Theorem 4:Let a/b∈(2,5/2)∪(5/2,8/3]. By Lemma 9, there is a graphGa/bwith properties (P1),(P2). By Lemma 10,Ka/bis universal. This concludes our result.

References

[1] Z. Hedrl´ın, On universal partly ordered sets and classes, J. Algebra 11(1969),503-509.

[2] P.Hell, J. Neˇsetˇril, Graphs and Homomorphisms, Oxford University Press, 2004.

[3] P.Hell, X. Zhu, The circular chromatic number of series-parallel graphs, J. Graph Theory, 33(2000),14-24.

[4] J. Hubiˇcka, J. Neˇsetˇril, Universal Partial Order Represented by Means of Trees and Other Simple Graphs, (to appear in European J. Comb.)

[5] J. Hubiˇcka, J. Neˇsetˇril , Finite Paths are Universal, ITI Series 2003-129, Charles University, 2003 (to appear in Order)

[6] W. Klostermeyer, C.Q. Zhang, (2 +)-coloring of planar graphs with prescribed girth, J. Graph Theory, 33(2000) (2):109-119.

[7] J. Neˇsetˇril, Y. Nigussie, Density of universal classes of series-parallel graphs (KAM Series 2004-717) [8] I. Niven, H. Zuckerman and H. Montgomery, An introduction to the Theory of Numbers, Hojn Wiley

& Sons, Inc., Fifth Edition, 1991.

[9] Z. Pan, X. Zhu, Density of the circular chromatic number series-parallel graphs, J. Graph Theory, 46(2004), 57-68.

[10] X. Zhu, Circular Chromatic Number, a survey. Discrete Mathematics, Vol.229 (1-3)(2001), 371-410.