# Vertex-coloring edge-weighting of bipartite graphs with two edge weights.

Let G be a graph and S be a subset of Z. A vertex-coloring S-edge-weighting of G is an assignment of weights by the elements of S to each edge of G so that adjacent vertices have different sums of incident edges weights.

It was proved that every 3-connected bipartite graph admits a vertex-coloring S-edge-weighting for S = {1,2} (H. Lu, Q. Yu and C. Zhang, Vertex-coloring 2-edge-weighting of graphs, European J. Combin., 32 (2011), 22-27). In this paper, we show that every 2-connected and 3-edge-connected bipartite graph admits a vertex-coloring S-edge-weighting for S [member of] {{0,1}, {1,2}}. These bounds we obtain are tight, since there exists a family of infinite bipartite graphs which are 2-connected and do not admit vertex-coloring S-edge-weightings for S [member of] {{0,1}, {1,2}}.

Keywords: edge-weighting, vertex-coloring, 2-connected, bipartite graph

1 Introduction

In this paper, we consider only finite, undirected and simple connected graphs. For a vertex v of graph G = (V, E), [N.sub.G](v) denotes the set of vertices which are adjacent to v and [d.sub.G](v) = |NG(v)| is called the degree of vertex v. Let [delta](G) and [DELTA](G) denote the minimum degree and maximum degree of graph G, respectively. For v [member of] V(G) and r [member of] [Z.sup.+], let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If v [member of] V(G) and e [member of] E(G), we use v ~ e to denote that v is an end-vertex of e. For two disjoint subsets S, T of V(G), let EG(S, T) denote the subset of edges of E(G) with one end in S and other end in T and let [e.sub.G](S, T) = |[E.sub.G](S, T)|. Let G = (U, W, E) denote a bipartite graph with bipartition (U, W) and edge set E.

Let S be a subset of Z. An S-edge-weighting of a graph G is an assignment w : E(G) [right arrow] S. An S-edge-weighting w of a graph G induces a coloring of the vertices of G, where the color of vertex v, denoted by c(v), is [[summation].sub.e~v] w(e). An S-edge-weighting of a graph G is a vertex-coloring if for every edge e = uv, c(u) [not equal to] c(v) and we say that G admits a vertex-coloring S-edge-weighting. If S = {1, 2,... , k}, then a vertex-coloring S-edge-weighting of a graph G is usually called a vertex-coloring k-edge-weighting.

For vertex-coloring edge-weighting, Karonski et al. (2004) posed the following conjecture:

Conjecture 1.1 Every graph without isolated edges admits a vertex-coloring 3-edge-weighting.

This conjecture is still wide open. Karonski et al. (2004) showed that Conjecture 1.1 is true for 3-colorable graphs. Recently, Kalkowski et al. (2010) showed that every graph without isolated edges admits a vertex-coloring 5-edge-weighting. This result is an improvement on the previous bounds on k established by Addario-Berry et al. (2007), Addario-Berry et al. (2008), and Wang and Yu (2008), who obtained the bounds k = 30, k = 16, and k = 13, respectively.

Many graphs actually admit a vertex-coloring 2-edge-weighting (in fact, experiments suggest (see Addario-Berry et al. (2008)) that almost all graphs admit a vertex-coloring 2-edge-weighting), however it is not known which ones do not. Khatirinejad et al. (2012) explored the problem of classifying those graphs which admit a vertex-coloring 2-edge-weighting. Chang et al. (2011) had made some progress in determining which classes of graphs admit vertex-coloring 2-edge-weighting, and proved that there exists a family of infinite bipartite graphs (e.g., the generalized [theta]-graphs) which are 2-connected and admit a vertex-coloring 3-edge-weighting but not vertex-coloring 2-edge-weightings. Lu et al. (2011) showed that every 3-connected bipartite graph admits a vertex-coloring 2-edge-weighting.

We write

[G.sub.12] = {G | G admits a vertex-coloring {1,2}-edge-weighting};

[G.sub.1] = {G | G admits a vertex-coloring {0,1}-edge-weighting};

[G*.sub.12] = {G | G is bipartite and admits a vertex-coloring {1,2}-edge-weighting};

[G*.sub.01] = {G | G is bipartite and admits a vertex-coloring {0,1}-edge-weighting}.

Dudek and Wajc (2011) showed that determining whether a graph belongs to [G.sub.12] or [G.sub.01] is NP-complete. Moreover, they showed that [G.sub.12] [not equal to] [G.sub.01]. The counterexamples constructed by Dudek and Wajc (2011) are non-bipartite.

Now we construct a bipartite graph, which admits a vertex-coloring 2-edge-weighting but not vertex-coloring {0, 1}-edge-weightings. Let [C.sub.6] be a cycle of length six and [GAMMA] be a graph obtained by connecting an isolated vertex to one of the vertices of [C.sub.6]. Take two disjoint copies of [GAMMA]. Connect two vertices of degree one of the two copies and this gives a connected bipartite graph G. It is easy to prove that G admits a vertex-coloring 2-edge-weighting but not vertex-coloring {0, 1}-edge-weighting. Hence [G*.sub.01] [not equal to] [G*.sub.12]. Next we would like to propose the following problem.

Problem 1 Determining whether a graph G [member of] [G*.sub.12] or G [member of] [G*.sub.01] is polynomial?

In this paper, we characterize bipartite graphs which admit a vertex-coloring S-edge-weighting for S[member of]{{0,1},{1,2}}, and obtain the following result.

Theorem 1.2 Let G be a 3-edge-connected bipartite graph G = (U, W, E) with minimum degree [delta](G). If G contains a vertex u of degree [delta](G) such that G - u is connected, then G admits a vertex-coloring S-edge-weighting for S [member of] {{0,1}, {1, 2}}.

By Theorem 1.2, it is easy to obtain the following result, which improves and extends the result obtained by Lu et al. (2011).

Theorem 1.3 Every 2-connected and 3-edge-connected bipartite graph G = (U, W, E) admits a vertex-coloring S-edge-weighting for S [member of] {{0,1}, {1,2}}.

So far, all known counterexamples of bipartite graphs, which do not have vertex-coloring {0, 1}-edge-weightings or vertex-coloring {1, 2}-edge-weightings are graphs with minimum degree 2. So we would like to propose the following problem.

Problem 2 Does every bipartite graph with [delta](G) [greater than or equal to] 3 admit a vertex-coloring S-edge-weighting, where S [member of] {{0,1}, {1, 2}}.

A factor of a graph G is a spanning subgraph. For a graph G, there is a close relationship between 2-edge-weighting and graph factors. Namely, a 2-edge-weighting problem is equivalent to finding special factors of graphs (see Addario-Berry et al. (2007) and Addario-Berry et al. (2008)). So to find factors with pre-specified degree is an important part of edge-weighting.

Let g, f : V(G) [right arrow] Z be two integer-valued functions such that g(v) [less than or equal to] f(v) and g(v) [equivalent to] f(v) (mod 2) for all v [member of] V(G). A factor F of G is called (g, f)-parity factor if g(v) [less than or equal to] dF(v) [less than or equal to] f(v) and [d.sub.F](v) [equivalent to] f(v) (mod 2) for all v [member of] V(G). For X [[subset].bar] V(G), we write g(X) = [[summation].sub.x[member of]X] g(x) and f(X) is defined similarly. For (g, f) -parity factors, Lovasz obtained a sufficient and necessary condition.

Theorem 1.4 (Lovasz (1972)) A graph G contains a (g, f)-parity factor if and only if for any two disjoint subsets S and T of V(G), it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [tau](S, T) denotes the number of components C, called g-odd components of G - S - T such that g(V(C)) + [e.sub.G](V(C), T) = 1 (mod 2).

In the proof of the main theorems, we also need the following three lemmas.

Theorem 1.5 (Chang et al. (2011)) Every non-trivial connected bipartite graph G = (A, B, E) with |A| even, admits a vertex-coloring 2-edge-weighting w such that c(u) is odd for u [member of] A and c(v) is even for v [member of] B.

Theorem 1.6 (Chang et al. (2011)) Let r [greater than or equal to] 3 be an integer. Every r-regular bipartite graph G admits a vertex-coloring 2-edge-weighting.

Theorem 1.7 (Khatirinejad et al. (2012)) Every r-regular graph G admits a vertex-coloring 2-edge-weighting if and only if it admits a vertex-coloring {0,1}-edge-weighting.

2 Proof of Theorem 1.2

Corollary 2.1 Every non-trivial connected bipartite graph G = (A, B, E) with |A| even admits a vertex-coloring {0,1}-edge-weighting.

Proof: By Theorem 1.5, G admits a vertex-coloring 2-edge-weighting w such that c(u) is odd for u [member of] A and c(v) is even for v [member of] B. Let w'(e) = 0 if w(e) = 2 and w'(e) = 1 if w(e) = 1. Then w' is a vertex-coloring {0,1}-edge-weighting of graph G. []

For completing the proof of Theorem 1.2, we need the following two technical lemmas.

Lemma 2.2 Let G be a bipartite graph with bipartition (U,W), where |U| [equivalent to] |W| [equivalent to] 1 (mod 2). Let [delta](G) = [delta] and u [member of] U such that [d.sub.G](u) = [delta]. If one of the following two conditions holds, then G contains a factor F such that dp(u) = [delta], [d.sub.F](x) [equivalent to] [delta] + 1 (mod 2) for all x [member of] U - u, dp(y) [equivalent to] [delta] (mod 2) for all y [member of] W and dp(y) [less than or equal to] [delta] - 2 for all y [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(i) [delta](G) [greater than or equal to] 4, G is 3-edge-connected and G - u is connected.

(ii) [delta](G) = 3, G is 3-edge-connected and |[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]| [less than or equal to] 2.

Proof: Let M be an integer such that M [greater than or equal to] [DELTA](G) and M [equivalent to] [delta] (mod 2). Let m [member of] {0,-1} such that m [equivalent to] [delta] (mod 2). Let g, f : V(G) [right arrow] Z such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By definition, we have g(v) [equivalent to] f(v) (mod 2) for all v [member of] V(G). It is sufficient for us to show that G contains a (g, f)-parity factor. Indirectly, suppose that G contains no (g, f)-parity factors. By Theorem 1.4, there exist two disjoint subsets S and T such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [tau](S, T) denotes the number of g-odd components of G - S - T. Since f(V(G)) is even, by parity, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

Hence S [union] T [not equal to] [??]. We choose S and T such that S [union] T is minimal. Let A = V(G) - S - T.

Claim 1. T [[subset].bar] {u}.

Otherwise, let v [member of] T - u and T' = T - v. We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

contradicting the choice of S and T.

Claim 2. S [[subset].bar] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Otherwise, suppose that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and let v [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let S' = S - v. We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

contradicting the choice of S and T again.

We write [tau](S, T) = [tau]. By Claims 1 and 2, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

i.e.,

([delta] - 2 - |T|)|S| + 2 [less than or equal to] [tau], (2)

which implies [tau] [greater than or equal to] 2 since |T| [less than or equal to] 1.

Since G - u is connected, we may see that S = 0. Note that G is 3-edge-connected, by Claims 1 and 2, we have

3[tau] [less than or equal to] [e.sub.G](A, S [union] T) = [e.sub.G](A, S) + [e.sub.G](A, T) [less than or equal to] ([delta] - |T|)|S| + |T|([delta] - |S|) (by Claims 1 and2) = ([delta] - 2|T|)|S| + |T|[delta],

i.e.,

3[tau] [less than or equal to] ([delta] - 2|T|)|S| + |T|[delta]. (3)

Combining (2) and (3), we may see that

[delta]|T| [greater than or equal to] (2[delta] - |T| - 6)|S| + 6. (4)

If [delta] [greater than or equal to] 4, then we have

[delta] [greater than or equal to] [delta]|T| (since |T| [less than or equal to] 1) [greater than or equal to] (2[delta] - |T| - 6)|S| + 6 (since |S| [greater than or equal to] 1) [greater than or equal to] 2[delta] - |T| [greater than or equal to] 2[delta] - 1,

a contradiction. So we may assume that [delta] = 3. Note that |S| [less than or equal to] |[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]| [less than or equal to] 2. By (4), we have

3 = [delta] [greater than or equal to] [delta]|T| [greater than or equal to] -|T||S| + 6 [greater than or equal to] 4, (5)

This completes the proof. []

Lemma 2.3 Let G be a bipartite graph with bipartition (U,W), where |U| [equivalent to] |W| [equivalent to] 1 (mod 2). Let [delta](G) = [delta] and u [member of] U such that [d.sub.G](u) = [delta]. If one of the following two conditions holds, then G contains a factor F such that [d.sub.F](u) = 0, [d.sub.F](x) [equivalent to] 1 (mod 2) for all x [member of] U - u, [d.sub.F](y) [equivalent to] 0 (mod 2) for all x [member of] W and [d.sub.F](y) [greater than or equal to] 2 for ally [member of] [N.sub.G](u).

(i) [delta](G) [greater than or equal to] 4, G is 3-edge-connected and G - u is connected.

(ii) [delta](G) = 3, G is 3-edge-connected and there exists a vertex v [member of] [N.sub.G](u) such that [d.sub.G](v) > 3.

Proof: Let M be an even integer such that M [greater than or equal to] [DELTA](G). Let g, f : V(G) [right arrow] Z such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Clearly, g(v) [equivalent to] f(v) (mod 2) for all v [member of] V(G) and g(V(G)) is even. It is also sufficient for us to show that G contains a (g, f) -parity factor.

Indirectly, suppose that G contains no (g, f)-parity factors. By Theorem 1.4, there exist two disjoint subsets S and T such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (6)

where [tau](S, T) denotes the number of g-odd components of G - S - T. We choose S and T such that S [union] T is minimal. Let A = V(G) - S - T.

Claim 1. S [[subset].bar] {u}.

Otherwise, suppose that there exists a vertex v [member of] S - u. Let S' = S - v. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

contradicting the the choice of S [union] T.

Claim 2. T [[subset].bar] [N.sub.G](u).

Otherwise, suppose that T - [N.sub.G](u) [not equal to] [??]. Let x [member of] T - [N.sub.G](u) and let T" =T - x. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

contradicting the choice of S [union] T.

By Claims 1 and 2, we may see that f(S) = 0 and g(T) = 2|T|. For simplicity, we write [tau](S, T) = [tau]. By (6), we see that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (7)

which implies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (8)

Note that G - u is connected, so we have |T| [greater than or equal to] 1. Since G is 3-edge-connected, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

i.e.,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (9)

Inequalities (7) and (9) implies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

i.e.,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (10)

If [delta] [greater than or equal to] 4, by (10), it follows

7|T| [greater than or equal to] 6 + [delta](2|T| - 1) [greater than or equal to] 8|T| + 2,

a contradiction. So we may assume that [delta] = 3. By condition (ii), [[summation].sub.x[member of]T] [d.sub.G](x) [greater than or equal to] 3|T| + 1. Combining (10),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which implies |T| [greater than or equal to] 5, a contradiction since |T| [less than or equal to] |[N.sub.G](u)| [less than or equal to] 3.

This completes the proof. []

Proof of Theorem 1.2: By Theorem 1.5 and Corollary 2.1, we can assume that both |A| and |B| are odd.

Firstly, we consider S = {0,1}. If G is 3-regular, by Theorem 1.6, then G admits a vertex-coloring 2-edge-weighting. By Theorem 1.7, G also admits a vertex-coloring {0,1}-edge-weighting. So we can assume that [delta](G) [greater than or equal to] 3 and G is not 3-regular. If [delta](G) = 3, since G is 3-edge-connected, then G - x is connected for every vertex x of G with degree three. Hence there exists a vertex v with degree three such that [N.sub.G](v) contains a vertex with degree at least four. Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Without loss generality, we may assume that u* [member of] U and so it is a vertex satisfying the conditions of Lemma 2.3. Hence by Lemma 2.3, G contains a factor F, which satisfies the following three conditions.

(i) [d.sub.F](u*) = 0;

(ii) [d.sub.F](x) [equivalent to] 1 (mod 2) for all x [member of] U - u*;

(iii) [d.sub.F](y) [equivalent to] 0 (mod 2) for all x [member of] W and [d.sub.F](y) [greater than or equal to] 2 for all y [member of] [N.sub.G](u*).

Clearly, [d.sub.F](x) [not equal to] [d.sub.F](y) for all xy [member of] E(G). We assign weight 1 for each edge of E(F) and weight 0 for each edge of E(G) - E(F). Then we obtain a vertex-coloring {0,1}-edge-weighting of graph G.

Secondly, we show that G admits a vertex-coloring 2-edge-weighting. By Theorem 1.6, we may assume that G is not 3-regular. If [delta] = 3, since G is 3-edge-connected, then G contains a vertex v' such that [d.sub.G](v') = 3, G - v' is connected and |[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]| [less than or equal to] 2. Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then u* is a vertex satisfying the conditions of Lemma 2.2. Hence by Lemma 2.2, G contains a factor F such that

(i) [d.sub.F](u*) = [delta];

(ii) [d.sub.F](x) [equivalent to] [delta] (mod 2) for all x [member of] W and [d.sub.F] (x) [less than or equal to] [delta] - 2 for all x [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];

(iii) [d.sub.F](y) [equivalent to] [delta] + 1 (mod 2) for all y [member of] U - u*.

Let w : E(G) [right arrow] {1,2} be a 2-edge-weighting such that w(e) = 1 for each e [member of] E(F) and w(e') = 2 for each e' [member of] E(G) - E(F). Clearly, c(u*) = [delta]. If y [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], since there exists an edge e ~ y such that e [??] E(F), then c(y) = [[summation].sub.e~y] w(e) > [delta]. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then c(y) [greater than or equal to] [d.sub.G](y) > [delta]. Hence c(y) [not equal to] c(u*) for all y [member of] [N.sub.G](u*). For each xy [member of] E(G), where x [member of] U - u* and y [member of] W, by the choice of F, we have c(x) [equivalent to] [delta] + 1 (mod 2) and c(y) [equivalent to] [delta] (mod 2). Hence w is a vertex-coloring {1,2}-edge-weighting of the graph G.

This completes the proof. []

Corollary 2.4 Let G be a 3-edge-connected bipartite graph. If 3 [less than or equal to] [delta](G) [less than or equal to] 5, then G admits a vertex-coloring S-edge-weighting for S [member of] {{0,1}, {1,2}}.

Proof: Since 3 [less than or equal to] [delta] [less than or equal to] 5 and G is 3-edge-connected, then for every vertex v of degree [delta], G - v is connected. By Lemma 2.2 and Theorem 1.2, with the same proof, G admits a vertex-coloring S-edge-weighting for S G {{0,1}, {1,2}}. []

3 Conclusions

In this paper, we prove that every 2-connected and 3-edge-connected bipartite graph admits a vertex-coloring S-edge-weighting for S [member of] {{0,1}, {1,2}}. The generalized [theta]-graphs is 2-connected and has a vertex-coloring 3-edge-weighting but not vertex-coloring {0,1}-edge-weighting or vertex-coloring 2-edge-weighting. So it is an interesting problem to classify all 2-connected bipartite graphs admitting a vertex-coloring S-edge-weighting. Since the parity-factor problem is polynomial, then there exists a polynomial algorithm to find a vertex-coloring S-edge-weighting of bipartite graphs satisfying the conditions of Theorem 1.2.

Acknowledgements

The authors would like to thank the anonymous Reviewer for all valuable comments and suggestions to improve the quality of our paper.

References

L. Addario-Berry, R. E. L. Aldred, K. Dalal, and B. A. Reed. Vertex coloring edge partitions. J. Combinatorial Theory Ser. B, 94:237-244, 2005.

L. Addario-Berry, K. Dalal, C. McDiarmid, B. A. Reed, and A. Thomason. Vertex-coloring edge-weightings. Combintorica, 27:1-12, 2007.

L. Addario-Berry, K. Dalal, and B. A. Reed. Degree constrained subgraphs. Discrete Applied Math., 156: 1168-1174, 2008.

J. Akiyama and M. Kano. Factors and Factorizations of Graphs--Proof Techniques in Factor Theory. Springer-Verlag Berlin Heidelberg, 2011.

G. Chang, C. Lu, J. Wu, and Q. Yu. Vertex coloring 2-edge weighting of bipartite graphs. Taiwanese J. Math., 15:1807-1813, 2011.

A. Dudek and D. Wajc. On the complexity of vertex-coloring edgeweightings. Discrete Math. Theor. Comput. Sci., 13:45-50, 2011.

M. Kalkowski, M. Karonski, and F. Pfender. Vertex-coloring edge-weightings: towards the 1-2-3-conjecture. J. Combin. Theory Ser. B, 100:347-349, 2010.

M. Karonski, T. Luczak, and A. Thomason. Edge weights and vertex colors. J. Combin. Theory Ser. B, 91:151-157, 2004.

M. Khatirinejad, R. Naserasr, M. Newman, B. Seamone, and B. Stevens. Vertex-colouring edge-weightings with two edge weights. J. Combin. Theory Ser. B, 14:1-20, 2012.

L. Lovasz. The factorization of graphs II. Acta Math. Acad. Sci. Hungar., 23:223-246, 1972.

H. Lu, Q. Yu, and C. Zhang. Vertex-coloring 2-edge-weighting of graphs. European J. Combin., 32: 22-27, 2011.

T. Wang and Q. Yu. A note on vertex-coloring 13-edge-weighting. Frontier Math. in China, 3:1-7, 2008.

Hongliang Lu ([dagger])

School of Mathematics and Statistics, Xi'an Jiaotong University, Xi'an, PR China

received 28th Feb. 2015, revised 29th Oct. 2015, accepted 9th Dec. 2015.

(*) This work was supported by the National Natural Science Foundation of China No. 11471257 and the Fundamental Research Funds for the Central Universities.

([dagger]) Corresponding email: luhongliang215@sina.com
Author: Printer friendly Cite/link Email Feedback Lu, Hongliang DMTCS Proceedings Report Jan 1, 2016 3858 How often should you clean your room? Avoiding patterns in irreducible permutations. Graphic methods Mathematical research