ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 16 (2019) 173-182 https://doi.org/10.26493/1855-3974.1017.0ac (Also available at http://amc-journal.eu) F-WORM colorings of some 2-trees: partition vectors Julian D. Allagan Department of Mathematics and Computer Science, Elizabeth City State University, Elizabeth City, North Carolina, USA Vitaly Voloshin Department ofMathematics and Geomatics, Troy University, Troy, Alabama, USA Received 24 January 2016, accepted 28 May 2018, published online 21 November 2018 Suppose F = {F1,... ,Ft} is a collection of distinct subgraphs of a graph G = (V,E). An F-WORM coloring of G is the coloring of its vertices such that no copy of each subgraph Fj G F is monochrome or rainbow. This generalizes the notion of F-WORM coloring that was introduced recently by W. Goddard, K. Wash, and H. Xu. A (restricted) partition vector ((a,..., Q) is a sequence whose terms Zr are the number of F-WORM colorings using exactly r colors, with a < r < p. The partition vectors of complete graphs and those of some 2-trees are discussed. We show that, although 2-trees admit the same partition vector in classic proper vertex colorings which forbid monochrome K2, their partition vectors in K3-WORM colorings are different. Keywords: 2-tree, maximal outerplanar, partition, Stirling numbers. Math. Subj. Class.: 05C15, 05C10 1 Preliminaries A partition a of a set S is a set of nonempty subsets or blocks of S such that each element of S is in exactly one of the subsets of S. The number of blocks of a is its rank and a partition of rank r is simply called an r-partition. For instance, the Stirling number of the second kind, {"} counts the number r-partitions of the set [n] = {1,2,... ,n}. Consider the mapping c: S ^ [x] being an x-coloring of the elements of S. A subset A C S is said to be monochrome if all of its elements share the same color and A is rainbow if all of its elements have different colors. As such, a coloring c(S) is a partition of the set E-mail addresses: aallagan@gmail.com (Julian D. Allagan), vvoloshin@troy.edu (Vitaly Voloshin) Abstract ©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/ 174 Ars Math. Contemp. 16 (2019) 141-155 S since all of the elements of S are assigned a color; elements that share the same color belong to the same block (monochrome subsets), and different blocks are used for those with distinct colors (rainbow subsets). Let G = (V, E) denote a simple graph and suppose F = {Fi,..., Ft} is a collection of some distinct subgraphs Fj C G, 1 < i < t. An F-WORM coloring of G is the coloring of the vertices of G such that no copy of each subgraph Fj is monochrome or rainbow. When F has only one member, say F, we write F-WORM coloring; this special case was first introduced by W. Goddard, K. Wash and H. Xu, and independently studied by Cs. Bujtas and Zs. Tuza [5, 7, 8, 12, 13]. We note that this coloring requirement makes sense only if each Fj G F is of order three or more. However, for a generalization purpose if some Fj is of order 2, we allow only rainbow copies of Fj in order to meet the classic proper (vertex) coloring requirement. Suppose H = (V, E) is a hypergraph. If |e| = s for each hyperedge e G E, then H is said to be s-uniform. Given any vertex coloring of H, if no e G E is monochrome, H is called a D-hypergraph or simply a hypergraph. When no e G E is rainbow, H is called a cohypergraph. In the event no e G E is monochrome or rainbow, then H is called a bihypergraph. Moreover, if G is a hypergraph and each subgraph Fj = Er, the null graph on r-vertices, then an F-WORM coloring of G is a proper (vertex) coloring of an r-uniform bihypergraph; Cs. Bujtas and Zs. Tuza [7, 8] also noted this strong relation between F-WORM coloring and mixed hypergraph colorings, a theory that was first introduced by the second author [25, 26]. Thus, the notion of F-WORM colorings generalizes several well known coloring constraints. Given an F-WORM coloring, the sequence ((a,..., (p) whose terms, (r, are the number of r-partitions is called a (restricted) partition vector, with a < r < p. In general, partition vectors have some added benefits in the study of log-concave and unimodal sequences which often arise in algebra, combinatorics, computer science, even in probability and statistics (see for e.g., [2,4, 11]). A sequence of non-negative terms (a0,... ,an) is called log-concave if a2 > aj-1aj+1 for i = 1,..., n - 1. Such sequence is also said to be unimodal if it has no gap (i.e., there is no i with aj-1 = 0, aj =0 and aj+1 = 0) and there is an index 0 < j < n such that a0 < ... < aj > ... > an. Further, partition vectors are closely related to colorings; each zr gives the number of F-WORM colorings using exactly r colors, in which case a and P are the lower and upper chromatic numbers, respectively. In [7], it is shown that it is NP-hard to determine a and it is NP-complete to decide whether or not a graph G admits a K3-WORM coloring using k > 2 colors. Moreover, the integer set S = {x : a < x < P} commonly known as feasible set, has been the subject of numerous research publications (see e.g., [6, 15, 18, 27]). We note that the term chromatic spectrum has also been used for feasible set in some of the aforementioned literatures. Further, we call the rank-generating function £ a(G|F; x) = ^ Zkxk k=a the restricted partition polynomial of G subject to an F-WORM coloring. Note that, when xj is replaced by the falling factorial power x- = x(x - 1)(x - 2) • • • (x - i + 1), the polynomial £ a(G|F; x) = ^ Zkxk k=a counts all F-WORM colorings using at most x colors. Some variants of restricted partition polynomials have been well studied. For instance when G = En, a(G|g; x) is the J. D. Allagan and V. Voloshin: F -WORM colorings of some 2-trees: partition vectors 175 Bell polynomial which is a widely studied tool in combinatorial analysis [9, 24]. Also, a(G|K2 ; x) has been recently called Stirling polynomial [11] although it was first introduced by Korfhage as a-polynomial [17]. In particular, when written in the falling factorial power of x, a(G|K2; x) = x(G; x) is the well known chromatic polynomial [3, 22]. Thus, a restricted partition polynomial extends both the chromatic polynomial and the Stirling polynomial of graphs. In this paper, in Section 2, we determine the partition vectors of some mixed hypergraphs. Later, in Section 3, we investigate K3-WORM colorings of some 2-trees. We find that, while 2-trees admit the same partition vector given any (classic) proper vertex coloring, it is not true for their K3-WORM colorings. To support this argument, we present two non-isomorphic members of 2-trees which have different partition vectors. In Section 4, we conclude this paper with F-WORM colorings when F includes a family of 2 or more graphs such as Path, Star or Cycle. 2 Coloring Kn with forbidden monochrome or rainbow subgraphs We begin by establishing a connection between Ks-WORM coloring of a complete graph Kn and mixed hypergraph colorings. Theorem 2.1. The partition vector in a Ks-WORM coloring of Kn is (([^J,..., Zs-1), where Zr = {n} for all 3 < s 3 of its vertex set is called an s-uniform complete hypergraph. Corollary 2.2. The partition vector of an s-uniform complete bihypergraph is (([^ J,.. Zs-1), where Zr = {n} for all s > 3. Removing either restriction on r gives each of the next result. Corollary 2.3. The partition vector of an s-uniform complete hypergraph is (Z[-^- j ,..., Zs), where Zr = {n} for all s > 2. Corollary 2.4. Thi partition vector of an s-uniform complete cohypergraph is (Z1,..., Zs-1), where Zr = {n} for all s > 3. 3 Partition vectors of some 2-trees As a generalization of a tree, a k-tree on n vertices (with 1 < k < n) is a graph which arises from a Kk by adding n — k > 1 new vertices, each joined to a Kk in the old graph; this process generates several non-isomorphic k-trees, k > 1. Figure 1 depicts four non-isomorphic 2-trees on 6 vertices. K-trees are chordal graphs which are known to admit at least one simplicial elimination ordering ([10]). Recall, a graph is chordal if it does not contain an induced cycle of length 4 or more. The characterization of families of graphs by forbidden subgraphs is an old tradition in graph theory and k-trees, despite 176 Ars Math. Contemp. 16 (2019) 141-155 (a) 3-sun (b) fan (c) snake (d) 0(1, 2, 2, 2, 2) Figure 1: Some non-isomorphic 2-trees. being ubiquitous, have yet to be fully classified even in the case when k = 1. Adding some additional restrictions on the coloring of certain subgraphs besides K2 and En may help in the analysis of the structure of the graphs that contain them. To help support this claim, we begin with the partition vectors in the coloring of 2-trees when monochrome K2 are forbidden. These vectors do not characterize any member of k-trees, since non-isomorphic k-trees do share the same partition vector as shown, later, in Corollary 3.2. Proposition 3.1. The equality n — k holds for all 1 < k < n. xk (x - k)n-k = y, \ '¡-l t=k+1 Proof Since xn = £"=1{"}x-, this implies that (x - k)n-k = {"T7(x - k)- and xk(x - k) n-k n-k = E t=1 n-k E t=1 E t=k + 1 n - k t n - k t n - k tk x(x - 1) • • • (x - k - 1)(x - k)- „t+k giving the result. □ Corollary 3.2. The partition vector of any k-tree on n — k simplicial vertices such that no K2 is monochrome is (Cfe+i,..., Cn), where Çr = {n-^} • Proof. It is easy to see that the left side of the equality of the formula in Proposition 3.1 is that of the chromatic polynomial of any k-tree, k > 1. The result follows from the right side of that equality. □ x J. D. Allagan and V. Voloshin: F -WORM colorings of some 2-trees: partition vectors 177 We note the quantity } = } ^ is known for counting the number of k-nonconse-cutive r-partitions of n elements (see e.g., [16]); a partition of the set {1,... ,n} is said to be k-nonconsecutive whenever x and y are in the same block, |x - y| > k. Recall that a graph is called outerplanar if it can be embedded in the plane in such a way that every vertex lies on the outer cycle. A maximal outerplanar (MOP) graph is an outerplanar graph with a maximum number of edges [21]. Graphs such as 3-sun, fan and snake are some well known MOPs; these graphs are depicted in Figures 1(a), 1(b) and 1(c), respectively. Laskar and Mulder [19,20] characterized MOPs as the intersection of any two of the following graphs: chordal, path-neighborhood, and triangle graphs T(G) which are trees. Recall, a path-neighborhood graph is a graph in which every vertex neighborhood induces a path and the triangle graph T(G) of G has the triangles of G as its vertices, and two vertices of T(G) are adjacent whenever their corresponding triangles in G share an edge [1]. Simply put, MOPs are members of 2-trees. Here, by considering K3-WORM colorings of 2-trees, we have found that their partition vectors are uniquely determined and the process reveals that MOPs are 2-trees with the characteristic that every edge is shared by at most two triangles. Theorem 3.3. Suppose G is a 2-tree such that its triangle graph is a path. Then the number of colorings of its vertices such that no triangle is monochrome or rainbow is P(G)= ^ 4>(n - 1j)x(x - 1)j, i(n — 1,j) -1,j + an-1,l n- j +j ifj < f O-n-1, \ otherwise and the values ai,j 's satisfying, (i) a11 = 1,ai1 = 2 for each 2 < i < n — 1 and, for each k (ii) 1,..., L2J, a2k, j = aik-1 ,j + a^k-1 ,j+k-1 if 2 < j < k a2k-1,j-k if k +1 < j < i (iii) a2k+1,j a2k,j + a2k,j+k-1 if 2 < j < k 1 a2k,j-k-1 if j = k + 1 if k + 2 < j < i. Proof. Suppose G = (V, E) is a 2-tree on n > 3 whose triangle graph is a path. Then, there exists a simplicial elimination ordering n = {u1,... ,un}, such that v,i is adjacent to the edge with endpoints (ui-1, ui-2). Let G1 := u1, G2 := u1u2, and Gi := Gi-1 U {ui} where ui is adjacent to the pair (ui-1,ui-2) in Gi for all i > 3. Suppose c is any coloring of G and denote by P(G) the restricted number of colorings of G. For n = 3, we count the colorings when u1 u2 is rainbow and when u1 u2 is monochrome, separately. If we denote a f 178 Ars Math. Contemp. 16 (2019) 141-155 A1 = x(x-1) andB1 = x thenP(G3) = A1 + (x- 1)Bi + Ai. Set A2 := A1 + (x- 1)Bi and B2 := Ai and clearly A2 and B2 count the number of colorings where c(u3) = c(u2) and c(u3) = c(u2), respectively. For all n > 3, at each iteration, we separate the terms that count c(uj) = c(ui_i) from those that count c(uj) = c(ui_i), giving the recursion P(G„) = A„_i + B„_i, where A„_i := A„_2 + (x - 1)B„_2 and A„_i := A„_2. Now use Ai and Bi as basis for the previous recursion and record at each iterative step the coefficients ai ,j's of each expression (x - 1)k, for 1 < i, j < n - 1. By letting aiji = 1, it is easy to verify that the coefficients ai}j's satisfy the conditions (i) - (iii). For instance, when n = 3, a2ji = 2, a2,2 = ai,i = 1. Now, define an (n - 1) x (n - 1) matrix A whose entries are the coefficients aiij-'s of P(Gi+i) with P(G2) = x(x - 1). It follows that P := xA • Q, where P and with Thus, P(G2) P (G3) , A = P (Gn)_ Q= q1 = (x - 1)1 Q2 = = (x - 1)1 = ai,i a2,i a2,2 an-i,i an-1,2 . . . an-in-1 Q = [Q1 I Q2]T, (x - 1)T^f11 (x - 1)L^f1 J and where E an_i,k(x - 1)k + £ an_i,k(x - 1)fc_r^i1 ^ = i 2, the sequence {bn} satisfies the shifted Fibonacci recurrence given by bi = 3, b2 = 5 and bn = bn-1 + bn-2, for n > 3. 180 Ars Math. Contemp. 16 (2019) 141-155 3. If each triangle of G is replaced by a hyperedge (of size 3), the previous result also gives the partition vector of several nonlinear 3-uniform acyclic bihypergraphs, which include the complete 3-uniform interval bihypergraphs [26]; 3-uniform bihypergraphs often appear in communication models for cyber security [14]. Obviously, there are other members of 2-trees who have 3 or more triangles sharing the same edge as subgraphs. Here, we present the other extremal case of 2-trees when all triangles share a single edge, say u1u2. This 2-tree, often denoted by 6(1,2,..., 2), is a member of the well known n-bridge graphs. See Figure 1(d) for an example of a 5-bridge. Note that 6(1, 2,..., 2) is a maximal planar graph but not a MOP, for all n > 5. Corollary 3.6. Suppose G = 6(1, 2,..., 2), an (n — 1)-bridge graph on n > 3 vertices. The partition vector of a K3-WORM coloring of G is (Z2,..., Cn-i) where 2n-2 + 1 if r = 2 Zr n 2\ otherwise. r1 Proof. Count the number of colorings when the shared edge wiw2 is monochrome and when it is rainbow, giving x(x - 1)n-2 + 2n-2x(x - 1) colorings. Now apply Proposition 3.1 (when k = 1) to the terms of the expression to obtain the result. □ We leave it to the reader to verify that the previous values in the partition vector when G = 6(1,2,..., 2) are different from those of MOPs, for all n > 5. 4 Conclusion We've shown that while 2-trees admit the same partition vector given any proper vertex coloring, it is not the case with their K3-WORM colorings. We hope these results indicate the importance of WORM colorings in general in the analysis of the structures of some well-known graphs which could not be classified with the usual proper vertex colorings. For a potential future research, we introduce some generalizations of F-WORM colorings when F includes multiple graphs such as Path, Star or Cycle. In the next results, Cn, K1n-1, and Pn denote an n-cycle, an n-star, and an n-path that includes a fixed vertex (apex) u1, respectively. Corollary 4.1. Suppose G is a fan on n > 4 vertices. If G has a K3-WORM coloring then G admits an F-WORM coloring with F = |Ps*,K1ji,Cr,6(1,n1,n2)} where s > 4, Ln—1J < t < n — 1, r > 3, and 2 < n1 < n2 such that n1 + n2 < n. Proof. Suppose G is a fan on n > 4 vertices which we can construct as follow: start with a triangle, say (u1,u2,u3), and iteratively add n — 3 new vertices such that each additional vertex u is adjacent to the pair (u1, ui-1), for i = 4,..., n. Assume G admits a K3-WORM coloring. (i) Observe that for s > 4, every path P* C G contains the subgraph u1uiui+1 for some i (2 < i < n — 2). If some 3-path (that includes u1 ) is monochrome/rainbow then the triangle (u1,ui,ui+1) is monochrome/rainbow, violating the K3-WORM coloring assumption. Hence G admits a PS*-WORM coloring for all s > 4. J. D. Allagan and V. Voloshin: F -WORM colorings of some 2-trees: partition vectors 181 (ii) By letting the vertices of K1jt C G be all the vertices of G, it follows that t < n - 1. Now, consider the coloring such c(ui) = c(u2k) and c(ui) = c(u2k+1) for k = 1,..., [n-1 ]. Clearly, such coloring does not violate our assumption of K3-WORM coloring of G. Hence, the lower bound of t is satisfied by letting the vertices of K1jt be {u1, u2} U {u2k+1 : k = 1,..., [n-1 ]}, which guarantees a K1jt-WORM coloring for all t > []. (iii) For r > 4, since every cycle Cr C G includes the apex u1, there exists an s < r such that P* C Cr, with 4 < s < r < n. From (i), G admits a Cr-WORM coloring. The case when r = 3 is trivial. (iv) Likewise, since 6(1, n1, n2) contains C1+q C G with q e {n1, n2}, the result follows from (iii) that, for all 2 < n1 < n2 such that n1 + n2 < n, G admits a 6(1, n1, n2)- WORM coloring. □ Note that the converse of the statement in Corollary 4.1 is not true. Using a similar argument as in the previous proof establishes the next result; recall, a snake (see Figure 1(c)) is a 3-sun-free maximal outerplanar graph with at least four vertices. Corollary 4.2. Suppose G is a snake on n > 4 vertices. If G has a K3-WORM coloring then G admits an F-WORM coloring, where F = {Cr, 6(1, 2,2)} with 3 < r < n. References [1] R. Balakrishnan, Triangle graphs, in: R. Balakrishnan, H. M. Mulder and A. Vijayakumar (eds.), Graph Connections, Allied Publishers Limited, New Delhi, 1999 p. 44, proceedings of the conference held at Cochin University of Science and Technology, Cochin, January 28-31, 1998. [2] E. Bertin and R. Theodorescu, On the unimodality of discrete probability measures, Math Z. 201 (1989), 131-137, doi:10.1007/bf01162000. [3] G. D. Birkhoff and D. C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946), 355-451, doi:10.1090/s0002-9947-1946-0018401-4. [4] F. Brenti, Expansions of chromatic polynomials and log-concavity, Trans. Amer. Math. Soc. 332 (1992), 729-756, doi:10.1090/S0002-9947-1992-1069745-7. [5] Cs. Bujtas, E. Sampathkumar, Zs. Tuza, M. S. Subramanya and C. Dominic, 3-consecutive C-colorings of graphs, Discuss. Math. Graph Theory 30 (2010), 393-405, doi:10.7151/dmgt. 1502. [6] Cs. Bujtas and Zs. Tuza, Uniform mixed hypergraphs: the possible numbers of colors, Graphs Combin. 24 (2008), 1-12, doi:10.1007/s00373-007-0765-5. [7] Cs. Bujtas and Zs. Tuza, K3-WORM colorings of graphs: lower chromatic number and gaps in the chromatic spectrum, Discuss. Math. Graph Theory 36 (2016), 759-772, doi:10.7151/dmgt. 1891. [8] Cs. Bujtas, Zs. Tuza and V. Voloshin, Hypergraph colouring, in: L. W. Beineke and R. J. Wilson (eds.), Topics in Chromatic Graph Theory, Cambridge University Press, Cambridge, volume 156 of Encyclopedia of Mathematics and its Applications, pp. 230-254, 2015, doi: 10.1017/cbo9781139519793.014. [9] C. B. Collins, The role of Bell polynomials in integration, J. Comput. Appl. Math. 131 (2001), 195-222, doi:10.1016/s0377-0427(00)00274-0. [10] G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961), 71-76, doi: 10.1007/bf02992776. 182 Ars Math. Contemp. 16 (2019) 141-155 [11] D. Galvin and D. T. Thanh, Stirling numbers of forests and cycles, Electron. J. Com-bin. 20 (2013), #P73, http://www.combinatorics.org/ojs/index.php/eljc/ article/view/v2 0i1p7 3. [12] W. Goddard, K. Wash and H. Xu, WORM colorings forbidding cycles or cliques, Congr. Numer. 219 (2014), 161-173. [13] W. Goddard, K. Wash and H. Xu, WORM colorings, Discuss. Math. Graph Theory 35 (2015), 571-584, doi:10.7151/dmgt.1814. [14] A. Jaffe, T. Moscibroda and S. Sen, On the price of equivocation in byzantine agreement, in: D. Kowalski and A. Panconesi (eds.), PODC'12, ACM Symposium on Principles of Distributed Computing, ACM, 2012pp. 309-318, doi:10.1145/2332432.2332491, proceedings of the 2012 ACM Symposium on Principles of Distributed Computing held in Funchal, Madeira, Portugal, July 16-18, 2012. [15] T. Jiang, D. Mubayi, Zs. Tuza, V. Voloshin and D. B. West, The chromatic spectrum of mixed hypergraphs, Graphs Combin. 18 (2002), 309-318, doi:10.1007/s003730200023. [16] Zs. Kereskenyi-Balogh and G. Nyul, Stirling numbers of the second kind and Bell numbers for graphs, Australas. J. Combin. 58 (2014), 264-274, https://ajc.maths.uq.edu.au/ pdf/58/ajc_v58_p264.pdf. [17] R. R. Korfhage,