ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 12 (2017) 351-360
From NMNR-coloring of hypergraphs to homogenous coloring of graphs
Mária Janicová Tomás Madaras Roman Sotak
Faculty of Science, Pavol Jozef Safárik University, Kosice, Slovakia
Borut Luzar *
Faculty of Information Studies, Novo mesto, Slovenia
Received 7 April 2016, accepted 20 November 2016, published online 31 January 2017
An NMNR-coloring of a hypergraph is a coloring of vertices such that in every hy-peredge at least two vertices are colored with distinct colors, and at least two vertices are colored with the same color. We prove that every 3-uniform 3-regular hypergraph admits an NMNR-coloring with at most 3 colors. As a corollary, we confirm the conjecture that every bipartite cubic graph admits a 2-homogenous coloring, where a k-homogenous coloring of a graph G is a proper coloring of vertices such that the number of colors in the neigborhood of any vertex equals k. We also introduce several other results and propose some additional problems.
Keywords: Homogenous coloring, mixed hypergraph, bi-hypergraph, NMNR-coloring. Math. Subj. Class.: 05C15, 05C65
1 Introduction
In this paper we continue the study of homogenous colorings of graphs initiated in [8], specifically focusing on regular bipartite graphs. We consider only finite graphs and hype-graphs. Every graph G = (V, E) is determined by the set of vertices V = V(G) and the set of edges E = E(G). For any undefined notions used in the paper we refer to the standard monograph [1]. Given a vertex-coloring p of a graph G, the palette of a vertex v, P (v), is the set of colors appearing in the neighborhood N (v) of v, i.e. P (v) = {p(u) | u G N (v)}. The cardinality of P(v) is denoted by p(v).
* corresponding author
E-mail addresses: maria.janicova@student.upjs.sk (Maria Janicova), tomas.madaras@upjs.sk (Tomas Madaras), roman.sotak@upjs.sk (Roman Sotak), borut.luzar@gmail.com (Borut Luzar)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
352
Ars Math. Contemp. 12 (2017) 383-413
A k-homogenous coloring of a graph G is a proper coloring of its vertices such that the palette of every vertex is of size k. The smallest number of colors (if it exists), for which G admits a k-homogenous coloring is called k-homogenous chromatic number and denoted
xh(G).
As observed in [8], only bipartite graphs admit a 1-homogenous coloring: every proper coloring of a bipartite graph with two colors is admissible. Additionally, every d-regular graph admits a d-homogenous coloring: assigning distinct color to every vertex does the job. In fact, the d-homogenous chromatic number of a d-regular graph G is equal to the chromatic number of the square graph G2, i.e. the graph with V(G2) = V(G) where two vertices are adjacent if they are at distance at most 2 in G.
In the other cases, the question whether a graph admits a homogenous k-coloring becomes harder. In particular, two types of problems arise: (a) for a given integer k and a graph G, does G admit a k-homogenous coloring; and (b) if (a) is answered in affirmative, what is the value of xh(G)?
A d-regular graph G is completely homogenous if it admits a k-homogenous coloring for every k, 1 < k < d. The motivation for this paper was given by the following conjecture.
Conjecture 1.1 (Janicova, 2015). Every cubic bipartite graph is completely homogenous.
As the cases with k g {1,3} are trivial as remarked above, it only remains to prove that there exists a 2-homogenous coloring of every cubic bipartite graph. To prove this, we make use of the results from the rich field of hypergraph colorings.
A hypergraph H = (V, e) is determined by a set of vertices V = V(H) and a set of (hyper)edges e = e(H), where every edge is an arbitrary subset of vertices. For an edge e, let V(e) denote the set of vertices incident to e. We say that H is k-uniform if every edge is incident to exactly k vertices, k-regular if every vertex is contained in exactly k edges, and linear if every two edges share at most one vertex.
Similarly as in the case of graphs, by a coloring p of a hypergraph H we mean an assignment of colors to the vertices of H. For an edge e g e, the palette of e, P(e), is the set of colors given to the vertices incident to e. Again, we define p(e) = |P(e)|. We say that an edge e of H is monochromatic if p(e) = 1, i.e. all the vertices incident to e are colored with the same color, and an edge is rainbow if p(e) = | V(e) |, i.e. no two vertices of e are colored with the same color. A coloring of H is non-monochromatic non-rainbow coloring (or a NMNR-coloring in short) if there is neither monochromatic edge nor rainbow edge in H.
The notion of NMNR-colorings arose from more general concepts of color-bounded hypergraphs introduced by Bujtas and Tuza in [2], where for every edge the lower and the upper bound on the palette size is given, and pattern hypergraphs introduced by Dvorak et al. in [6], where every hyperedge is assigned a set of admissible colors. Color-bounded hypergraphs generalize many coloring concepts in hypergraphs; they were inspired by the work of Drgas-Burchardt and Lazuka [5], who only set the lower bounds on the sizes of palettes, and the notion of mixed hypergraphs introduced by Voloshin [12, 13]. A mixed hypergraph M consists of the set of vertices and two families of edges, the C-edges and the D-edges. A coloring of the vertices of M is proper if no C-edge is rainbow and no D-edge is monochromatic. Study of mixed hypergraphs received considerable attention in the last two decades1 (cf. [10]). Interestingly, colorings of mixed hypergraphs are strongly related
1See also the web-page http://spectrum.troy.edu/voloshin/mh.html for more details.
M. Janicova et al.: From NMNR-coloring of hypergraphs to homogenous coloring of graphs 353
to various types of graph colorings as shown e.g. by Král' in [9].
If every edge of M is a C-edge and a D-edge, then M is called a bi-hypergraph. When a mixed hypergraph M is a bi-hypergraph, then a proper coloring of M is precisely an NMNR-coloring. We refer an interested reader to [3] and [4] for the most recent results in this field.
Now, we present the main results of the paper, thus solving Conjecture 1.1 in affirmative.
Theorem 1.2. Every cubic bipartite graph G admits a 2-homogenous coloring. Moreover,
Xh(G) < 6.
Theorem 1.2 is in fact a corollary of the following theorem:
Theorem 1.3. Every 3-regular 3-uniform hypergraph admits an NMNR-coloring with at most 3 colors.
The rest of the paper is structured as follows: in Section 2, we introduce some auxiliary results we use in the proofs of the main results. In Section 3, we prove Theorem 1.3, and in the last section, we present several additional results and conclude the paper with some open problems.
2 Auxiliaries
In this section we present some auxiliary results. First, we show how the problem of 2-homogenous coloring of a cubic bipartite graphs can be modeled with an NMNR-coloring of 3-uniform hypergraphs. Let G be a cubic bipartite graph and EG be a hypergraph with the vertex set V(Eg) = V(G) and the edge set e(HG) = {N(v) | v e V(G)}. Clearly, EG is 3-uniform, hence an NMNR-coloring of HG is a coloring assigning exactly two different colors to the vertices incident to every edge of HG, meaning that the palette of every vertex in G is of size 2. Hence, we immediately obtain the next proposition.
Proposition 2.1. Every cubic bipartite graph G admits a 2-homogenous coloring if and only if the hypergraph EG admits an NMNR-coloring.
Note that the bipartiteness of G is necessary to ensure that the coloring of G is proper, as we now see. The hypergraph HG is not connected, since no pair of vertices from distinct parts of G is incident to a common edge of HG. Let p be an NMNR-coloring of HG. Then, a 2-homogenous coloring p of G is obtained by assigning the color (i, p(v)) to the vertex v in G, where i e {1, 2} denotes the part of G the vertex v belongs to. This in particular means that at most twice the number of colors used for an NMNR-coloring of HG are used for a 2-homogenous coloring of G. On the other hand, each 2-homogenous coloring of G is also an NMNR-coloring of HG.
As G is cubic, Hg is also 3-regular, which enables us to use the following results on bipartite hypergraphs. A hypergraph is bipartite or 2-colorable if it admits a coloring of vertices with 2 colors such that no edge is monochromatic.
Theorem 2.2 (Henning and Yeo, 2013). For an integer k > 4, every k-regular k-uniform hypergraph is bipartite.
354
Ars Math. Contemp. 12 (2017) 383-413
The proof of Theorem 2.2 was given in [7], but the result was mentioned already earlier in [11].
For k = 3, there exist infinite families of non-bipartite 3-regular 3-uniform hypergraphs (cf. [7]), the Fano plane being the most famous example (see Fig. 1). The result however holds if the hypergraph is not regular.
Theorem 2.3 (Henning and Yeo, 2013). Every connected 3-uniform hypergraph with maximum degree at most 3 that is not 3-regular is bipartite.
Figure 1: The hypergraph of Fano plane is not bipartite.
Theorem 2.3 immediately implies the following corollary.
Corollary 2.4. Every connected 3-regular 3-uniform hypergraph is either bipartite or becomes bipartite after deleting any edge from it.
3 Proof of Theorem 1.3
First we prove a lemma about NMNR-colorings of linear 3-regular 3-uniform hypergraphs.
Lemma 3.1. Every linear 3-regular 3-uniform hypergraph admits an NMNR-coloring with at most three colors.
Proof. Let H be a connected 3-regular 3-uniform linear hypergraph. By Corollary 2.4, H is either bipartite, or H - e is bipartite, for any e G E(H). In the former case, the lemma trivially holds, so we may asume that H is not bipartite.
We prove the lemma by contradiction. Suppose that H does not admit an NMNR-coloring with at most three colors. Let es = (u, v, w) be an edge of H and p be a 2-coloring (with colors 0 and 1) of H - es. Consequently, es is monochromatic, and, without loss of generality, we may assume that p(u) = p(v) = p(w) = 0.
We distinguish two types of edges of H regarding p: an edge e is of type 0 if two vertices of e are colored with 0, and the third vertex is colored with 1, and analogously, e is of type 1, if one of its vertices is colored with 0, and the other two are colored with 1 . Define p(v) = 1 — p(v) and call it the complementary color of a vertex v.
First, we discuss the types of the edges incident to the vertices of a monochromatic edge.
Claim 3.2. Every vertex incident to a monochromatic edge is incident to an edge of type 0 and an edge of type 1 .
M. Janicova et al.: From NMNR-coloring of hypergraphs to homogenous coloring of graphs 355
Proof: Let e be a monochromatic edge of H. Without loss of generality, we may assume all the vertices of e are of color 0. Suppose to the contrary that there is a vertex of e, say x, incident to two edges of the same type. If x is incident to two edges of type 0, then we can recolor x to 1 (see the left case in Fig. 2), obtaining a 2-coloring of H, a contradiction. In the case when x is incident to two edges of type 1, we color x with the color 2 (see the
X/ /	T" / /	y
L- ^—/	v	-A-i—^—/	v	tV	-v	tv /	s.
(oX o o) -► (»X o o)	( o o) —► Q o o)
Figure 2: Recoloring of a vertex x incident to two edges of type 0 (on the left), and type 1 (on the right). Vertices of color 0 are depicted with empty circles, vertices of color 1 with full, and the vertex of color 2 as a cross.
right case in Fig. 2). Notice that all three edges incident to x are now bichromatic, and so we obtain an NMNR-coloring of H with at most 3 colors, a contradiction.	■
An alternating chain C = e^e^^... ek-1vk with respect to the coloring is a sequence of vertices and edges, where e0 is a monochromatic edge incident to v1, the vertices vj; vj+1 are incident to the edge e^ for 1 < i < k — 1, and ej is of type ^(v). The third vertex incident to ej is denoted v-+1. We say that an edge e, distinct from the edges of C, is a bow edge for C if at least two of its vertices are incident to some edges of C. An alternating chain C is wrapped if one of the vertices vk and v'k, say vk, is incident to some bow edge ek = (vk, x, y) and there is no bow edge for the alternating chain C = e0v1e1v2e2... ek_2vk-1. Consequently, if, say, x is incident to ej, then y is not incident to any edge of C, as H is linear and C' does not have bow edges.
In the following claim, we discuss the edges incident to the vertices of alternating chains without bow edges.
Claim 3.3. Let C = e0v1e1v2e2... e^_1v£ be an alternating chain without bow edges. Then, for every ej, 1 < i < £ — 1, each of the vertices vj+1 and v-+1 is incident to another edge of the same type as ej, and an edge of the opposite type.
Proof: Suppose to the contrary, that there exists i, 1 < i < £ — 1, for which the claim does not hold and choose the smallest such i. Then, we recolor each vj, 1 < j < i, with its complementary color, and obtain a 2-coloring of H with precisely one monochromatic edge ej, due to minimality of i. By applying Claim 3.2 to ej and vj+1 or vj+1, we obtain a contradiction on non-bipartiteness of H.	■
From Claims 3.2 and 3.3, and the fact that H is finite, it directly follows that there exists a wrapped alternating chain C = esv1e1v2e2... ek-1vk, for some k > 2 in H starting in some vertex of es, say u = v1.
356
Ars Math. Contemp. 12 (2017) 383-413
In what follows, we show that we can recolor some vertices of H using colors 0, 1, and 2 to obtain an NMNR-coloring with at most three colors. At every step of recoloring, at most one edge of H is monochromatic and the other ones are bichromatic. Note that, for simplicity, we always adjust the coloring y>, so ^ changes after every recoloring. Let i, 0 < i < k — 2, be the smallest integer such that the edge ej is incident to a vertex of the edge ek = (vk, x, y). Let x be the vertex incident to the edges ej and ek. Additionally, denote the edge incident to vk distinct from ek-1 and ek by ek+1. It is possible that ek+1 is also incident to some vertex of C, but, by the minimality of i, it may be incident only to some vertex incident to the edges ej, for j > i. As H is linear, ek+1 is not incident to x.
First, recolor all the vertices vj, for 1 < j < i, with the color ^(vj). Note that only ej becomes a monochromatic edge (see Fig. 3). Next, consider two cases regarding the vertex
eo
eo
ei
(o o (o) • (•)
vi
V2
Co o O
ei
vi
V2
Vk-1	vk
Figure 3: In a wrapped alternating chain we recolor the vertices from vi to vj to their complementary colors, where ej is the edge to which ek is wrapped.
x. In both cases, we may, without loss of generality, assume that ^>(vk) = 0.
(i) x = vj+1. Suppose first that <^(x) = 0. Then, <^(y) = 1, for otherwise ek would be monochromatic. If the edge ek+1 is of type 0, then recolor the vertex x to 2 and the vertex vk to 1. If the edge ek+1 is of type 1, then we consider two subcases. If i + 2 < k — 1, then recolor the vertices x and vk to 2, and the vertex vk-1 to 0. Otherwise, if i + 2 = k — 1, recolor x to 1, vk-1 to 0, and vk to 2. As vk-1 is not incident to ek+1, ^ is an NMNR-coloring in both subcases.
We may thus assume that y(x) = 1. By Claim 3.3, we have that ^>(y) = 1. Note that i + 1 < k — 1 in this case as H is linear. If the edge ek+1 is of type 1, then recolor x and vk to 2, and vk-1 to 0. In the case when ek+1 is of type 0, recolor x to 2, and vk to 1. This establishes the case (i).
(ii) x = vj+1. Suppose that y(x) = 0. As above, y(y) must be 1. Note that by Claim 3.2, the third edge x is incident to is of type 1. If the type of ek+1 is 0, then recolor x to 2 and vk to 1. If the type of ek+1 is 1, then recolor the vertices x and vk to 2, and the vertex vk-1 to 0.
Therefore, we may assume that y(x) = 1. Suppose first that y(y) = 1. Then, the third edge incident to x is of type 0. If ek+1 is of type 0, then recolor vk to 1, and x
M. Janicova et al.: From NMNR-coloring of hypergraphs to homogenous coloring of graphs 357
to 2. If ek+1 is of type 1, then recolor vk-1 to 0 and vk to 2, and, in the case when i +1 < k — 1, recolor also x to 2.
Suppose now that = 0. Then, the third edge incident to x is of type 1. If ek+1 is of type 0, then recolor vk to 1, and x to 0. Therefore, we may assume that the type of ek+1 is 1. Then, we recolor vk to 2, and x and vk-1 to 0.
This establishes the lemma.	□
Now, we are ready to prove Theorem 1.3 by considering non-linear 3-regular 3-uniform graphs.
Proof of Theorem 1.3. We prove the theorem by contradiction. Let H be a 3-regular 3-uniform hypergraph with the minimum number of vertices such that it does not admit an NMNR-coloring with at most 3 colors. By Lemma 3.1, H is not linear. Thus, we may assume that there exists a pair of edges e, f e E(H) having at least two vertices in common. If e and f are incident to the same three vertices, then H — e is bipartite by Corollary 2.3. Consequently, H is bipartite also and the theorem holds.
Hence, it remains to consider the case where e and f are incident to precisely two common vertices. Let e = (u, v, w) and f = (v, w, z). Suppose first that there is another edge g = (v, w, x) of H incident to the vertices v and w. Then, let H* be the hypergraph obtained from H by replacing the edges e, f and g with an edge e* = (u, z, x) and removing the vertices v and w. By the minimality of H, there exists an NMNR-coloring of H* with at most 3 colors. Without loss of generality, we may assume that p* (u) = (z) = 0 and (x) = 1. However, we can obtain an NMNR-coloring of H from by coloring the vertex v with 0 and w with 1 .
Thus, we may assume that there is no edge of H, apart from e and f, incident to both v and w. Now, let H* be the hypergraph obtained from H by identifying the edges e and f into an edge e* = (u, v*, z) (where v* corresponds to the vertices v and w in H). Again, since H* is smaller than H, there exists an NMNR-coloring of H* with at most 3 colors. In what follows, we show that can be extended to the vertices v and w. Denote the third edge of H containing v (resp. w) by g = (a, b, v) (resp. h = (w, c, d)). There are three possible configurations of g and h (up to symmetry) in terms of the vertices a, b and c, d, namely:
( i ) g = ( a, u, v ) , h = ( w, z, c) ; (ii) g = (a, u, v), h = (w, c, d), with d = z; and (iii) g = (a, b, v), h = (w, c, d), with b = u, d = z.
Note also that it is possible that some vertices of g and h coincide.
Without loss of generality, we may again assume that the vertices of e* are colored by the colors 0 and 1 only in ^>*. Clearly, if y*(u) = y*(z) = 1 and ^*(v*) = 0, then we color both, v and w, with 0 and obtain an NMNR-coloring of H with at most 3 colors. So, we may assume that ^*(v*) = 0 and either y*(u) = 0 and y*(z) = 1, or y*(u) = 1 and y*(z) = 0. In both cases, if j^*(a), ^*(b)} = {1} and j^*(a), ^*(b)} = {0, 2}, then color v with 1 and w with 0. Otherwise, if {^>*(c),^>*(d)} = {1} and {y*(c), ^*(d)} = {0,2}, then color v with 0 and w with 1. In the remaining cases, i.e. when {{^*(a),^*(b)}, {^*(c),^*(d)}} e {{1}, {0, 2}}, color v and w with the color 2. It is easy to verify that such a coloring results in an NMNR-coloring of H with at most 3 colors, which establishes the theorem.	□
358
Ars Math. Contemp. 12 (2017) 383-413
Finally, from Theorem 1.3, we derive the proof of Theorem 1.2.
Proof of Theorem 1.2. Let G be a cubic bipartite graph and EG the 3-regular 3-uniform hypergraph HG, whose existence is guaranteed by Proposition 2.1. By Theorem 1.3, there exists an NMNR-coloring of HG with at most 3 colors, and thus also a 2-homogenous coloring of G with at most 6 colors.	□
4 Conclusion
We have shown that every cubic bipartite graph G is completely homogenous and that xh(G) < 6. For the latter, we used a simple construction of coloring obtained by NMNR-coloring with at most 3 colors of the hypergraph HG modeling the neighborhoods in two parts of G. At least 3 colors must be used to color HG, but one does not always need to double the number of colors to guarantee that the coloring of G is proper. In fact, we believe that the following holds.
Conjecture 4.1. Let G be a cubic bipartite graph. Then
xh(G) < 4.
A computer verification shows that the conjecture is true for cubic bipartite graphs of order at most 26, and is tight as x\(K3,3) = 4.
When considering k-regular bipartite graphs for k > 4, the proof that they all admit a 2-homogenous coloring is much easier. Similarly as cubic bipartite graphs, by Proposition 2.1, one can model the ones with higher degree. Let G be a k-regular bipartite graph and Hg the k-regular k-uniform hypergraph modeling G. By Theorem 2.2, HG is bipartite, implying that no edge of HG is monochromatic, and clearly not rainbow, as only two colors are used. It immediately proves the following theorem.
Theorem 4.2. Every k-regular bipartite graph G, with k > 4, admits a 2-homogenous coloring. Moreover,
xh(G) < 4.
It is natural to ask, what if, for k > 4, the sizes of palettes are bigger than 2. Already in the class of 4-regular bipartite graphs, there are graphs which do not admit 3-homogenous colorings. However, among all 4-regular bipartite graphs of order at most 22, there are precisely two graphs not admitting a 3-homogenous coloring: the complete bipartite graph K5,5 without a perfect matching, and the bipartite complement of the Heawood graph, i.e. the complete bipartite graph K7,7 with a copy of the Heawood graph removed. Both graphs are depicted in Fig. 4.
An i-proper coloring of a hypergraph E is such that the palette size of every edge equals i. One can trivially generalize Proposition 2.1 into the following form.
Proposition 4.3. Every k-regular bipartite graph G admits an i-homogenous coloring if and only if the hypergraph EG admits an i-proper coloring.
A complete k-uniform hypergraph H^ is a hypergraph on n vertices with the edge set consisting of all k-element subsets of the vertex set. Let G be isomorphic to the complete bipartite graph Kn,n without a perfect matching. Then, each of the two components of the hypergraph HG is isomorphic to the complete (n - 1)-uniform hypergraph HJJ-1.
M. Janicova et al.: From NMNR-coloring of hypergraphs to homogenous coloring of graphs 359
Figure 4: The only two 4-regular bipartite graphs on at most 22 vertices which do not admit a 3-homogenous coloring. A K5j5 without a perfect matching on the left, and the bipartite complement of the Heawood graph on the right.
In [2], the authors, considered a more general notion of complete uniform color-bounded hypergraphs, with given lower and upper bounds for the sizes of edge palettes. Here, we only present the result, where the lower and the upper bounds are equal.
Proposition 4.4 (Bujtas, Tuza, 2009). The complete (n — l)-uniform hypergraph H^-1 admits an £-proper coloring if and only if £ G {1, n — 1} or
n—2
2 <
£ — 1
Hence, the above inequality holds whenever £ < n/2. Proposition 4.4 implies that the complete bipartite graph Kn n without a perfect matching is not completely homogenous for any n > 4. However, as discussed already above, it is not known if there exists some other infinite family of regular bipartite graphs which are not completely homogenous. Thus, the directions of further work are straightforward.
Question 1. Which k-regular bipartite graphs admit £-homogenous colorings, for k > 4
and 3 < £ < k — 1?
Problem 4.5. Classify completely homogenous k-regular bipartite graphs, for k > 4.
Question 2. For a k-regular bipartite graph G admitting an £-homogenous coloring, what is the order of Xh(G) as a function of k and £?
We conclude with a conjecture about 4-regular bipartite graphs.
Conjecture 4.6. Every 4-regular bipartite graph, distinct from K5,5 without a perfect matching and the bipartite complement of the Heawood graph, is completely homogenous.
Acknowledgement. We are grateful to the two anonymous referees for their remarks and suggestions. This work was supported by the Slovak Research and Development Agency under the Contract No. APVV-15-0116, the Slovak VEGA Grant 1/0368/16, and by Slovenian Research Agency Program P1-0383. B. LuZar acknowledges partial support by the National Scholarship Programme of the Slovak Republic.
360
Ars Math. Contemp. 12 (2017) 383-413
References
[1]	J. A. Bondy and U. S. R. Murty, Graph Theory, volume 244 of Graduate Texts in Mathematics, Springer, New York, 2008, doi:10.1007/978-1-84628-970-5.
[2]	C. Bujtas and Z. Tuza, Color-bounded hypergraphs, I: General results, Discrete Math. 309
(2009),	4890-4902, doi:10.1016/j.disc.2008.04.019.
[3]	Y. Caro and J. Lauri, Non-monochromatic non-rainbow colourings of a-hypergraphs, Discrete Math. 318 (2014), 96-104, doi:10.1016/j.disc.2013.11.016.
[4]	Y. Caro, J. Lauri and C. Zarb, Selective hypergraph colourings, Discrete Math. 339 (2016), 1232-1241, doi:10.1016/j.disc.2015.11.006.
[5]	E. Drgas-Burchardt and E. Lazuka, Chromatic polynomials of hypergraphs, Appl. Math. Lett. 20 (2007), 1250-1254, doi:10.1016/j.aml.2007.02.006.
[6]	Z. Dvorak, J. Kara, D. Kral' and O. Pangrac, Pattern hypergraphs, Electron. J. Combin. 17
(2010),	#R15.
[7]	M. A. Henning and A. Yeo, 2-colorings in k-regular k-uniform hypergraphs, Europ. J. Combin. 34 (2013), 1192-1202, doi:10.1016/j.ejc.2013.04.005.
[8]	M. Janicova, Okolia vrcholov v zafarbenych grafoch, Master's thesis, P. J. Safarik University in Kosice, 2015.
[9]	D. Kral', Mixed hypergraphs and other coloring problems, Discrete Math. 307 (2007), 923938, doi:10.1016/j.disc.2005.11.050.
[10]	Z. Tuza and V. Voloshin, Problems and results on colorings of mixed hypergraphs, in: Horizons of combinatorics, Springer, Berlin, volume 17 of Bolyai Soc. Math. Stud., pp. 235-255, 2008, doi:10.1007/978-3-540-77200-2_12.
[11]	S. Vishwanathan, On 2-coloring certain k-uniform hypergraphs, J. Combin. Theory Ser. A 101 (2003), 168-172, doi:10.1016/S0097-3165(02)00024-9.
[12]	V. Voloshin, The mixed hypergraphs, Comput. Sci. J. Moldova 1 (1993), 45-52.
[13]	V. Voloshin, On the upper chromatic number of a hypergraph, Australas. J. Combin. 11 (1995), 25-45.