# A Matrix Approach to Hypergraph Stable Set and Coloring Problems with Its Application to Storing Problem

Authors: Min Meng; Jun-e Feng
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

This paper considers the stable set and coloring problems of hypergraphs and presents
several new results and algorithms using the semitensor product of matrices. By the definitions
of an incidence matrix of a hypergraph and characteristic logical vector of a vertex subset,
an equivalent algebraic condition is established for hypergraph stable sets, as well as a new
algorithm, which can be used to search all the stable sets of any hypergraph. Then, the vertex
coloring problem is investigated, and a necessary and sufficient condition in the form of algebraic
inequalities is derived. Furthermore, with an algorithm, all the coloring schemes and minimum
coloring partitions with the givenq colors can be calculated for any hypergraph. Finally, one
illustrative example and its application to storing problem are provided to show the effectiveness
and applicability of the theoretical results.


---

## Body

## 1. Introduction

A hypergraphH=(V,ℰ) is composed of a finite set V and a collection ℰ of nonempty subsets of V, in which V is called the vertex set of H and ℰ is called the edge set of H. Thus, graphs are a special kind of hypergraphs with two vertices in each edge. One of the basic problems about hypergraph theory is the stable set problem, which has been widely applied in many research fields like network coding [1, 2]. Another basic problem about hypergraph theory is the coloring problem, which is one of NP-complete problems. There are various forms of hypergraph coloring such as vertex coloring, good coloring of edges, strong coloring, and equitable coloring. Graph coloring has been widely used in many real-life areas including scheduling and timetabling in engineering, register allocation in compilers, and air traffic flow management and frequency assignment in mobile [3–6]. The coloring problems of a special kind of graphs have been widely discussed in [7–9]. In recent years, there have been some references considering hypergraph theory, such as [10, 11]. It has been successfully applied to many different areas such as Markov decision process [12], complete simple games [13], linear programming [14], and cooperation structures in games [15]. And a few references have analyzed the colorability of different kinds of hypergraphs [16–18]. However, there are no proper algebraic algorithms for stable set and coloring problems of hypergraphs. Thus, they are still open problems and it is necessary for us to establish new formulations and algorithms.In recent years, Cheng et al. [19, 20] have proposed an effective tool, called the semitensor product (STP) of matrices. Via STP, Boolean networks can be converted into an algebraic form and many problems of Boolean networks, such as controllability and observability [21], fixed points and cycles [22], and control design problems [23–25], have been investigated. To learn more about the applications of STP, the readers can refer to [26–30].In this paper, we investigate the stable set and vertex coloring problems of hypergraphs and present some new results and algorithms via STP. By incidence matrix and characteristic logical vector (CLV), a necessary and sufficient condition, as well as a new algorithm, is established for hypergraph stable sets. Then, we study the vertex coloring problem. An algebraic equivalent condition and an algorithm for coloring problem are obtained. With the two algorithms, we can calculate all the stable sets and coloring schemes with the givenq colors for any hypergraph. The results we obtained in this paper are feasible and clear, illustrated by an example and a practical application to the storing problems. Compared to [31], which has considered the stable set and coloring problems of graphs by STP, the results we obtained seem to be the generalization of [31]. However, just applying the results about graphs in [31] to hypergraphs, we cannot get the similar results about hypergraphs. In fact, there are many differences. We use incidence matrix of hypergraphs, while Wang et al. in [31] have used adjacent matrix of graphs. The derivations are completely different since the fundamental techniques used are not the same. Thus, in our paper, the results are new and innovative in some ways.The remainder of this paper is organized as follows. Section2 introduces the preliminaries on STP and hypergraph theory. In Sections 3 and 4, we investigate the stable set and coloring problems, respectively, and provide the main results and algorithms of this paper. One illustrative example is also given in Section 3, and the application of coloring problem to storing problem is presented in Section 5 to show the effectiveness and applicability of the obtained results. Section 6 makes a brief conclusion.Before ending this section, we introduce some notations which will be used throughout this paper. Consider the following.(i)
ℳm×n is the set of m×n real matrices.(ii)
δni is the ith column of the identity matrix In.(iii)
Δn:={δni∣i=1,…,n}. Δ2:=Δ.(iv)
𝒟:={0,1}. Identify 1~δ21, 0~δ22; then, 𝒟~Δ.(v)
A∈ℳm×n is called a Boolean matrix, if all its entries are either 0 or 1. The set of m×n Boolean matrices is denoted by ℬm×n.(vi)
A matrixL∈ℳn×r is called a logical matrix if the columns of L, denoted by Col(L), belong to Δn. That is, Col(L)⊆Δn. And Coli(L) means the ith column of L. Denote the set of n×r logical matrices by ℒn×r.(vii)
IfL∈ℒn×r, by definition it can be expressed as L=[δni1δni2⋯δnir]. Briefly, we denote it by L=δn[i1i2⋯ir].(viii)
ForA=(aij), B=(bij)∈ℳm×n, A≥≥(≤≤,≫,≪)B means aij≥(≤,>,<)bij, for all i,j.(ix)
For a setS, |S| is the cardinality of S.(x)
A=Diag{A1,A2,…,Ar} is a block-diagonal matrix with Ai in the (i,i)th position (1≤i≤r).(xi)
LetA=(aij)∈ℳm×n, B∈ℳp×q. The Kronecker product of matrices A and B is defined as
(1)A⊗B:=[a11Ba12B⋯a1nBa21Ba22B⋯a2nB⋮⋮⋱⋮am1Bam2B⋯amnB].


## 2. Preliminaries

In this section, we will give some necessary preliminaries on STP and hypergraph theory, which will be used later.Definition 1 (see [20]).
LetA∈ℳm×n and B∈ℳp×q. The STP of matrices A and B, denoted by A⋉B, is defined as
(2)A⋉B=(A⊗Is/n)(B⊗Is/p),
where s=lcm{n,p} is the least common multiple of n and p.Remark 2.
Whenn=p, STP coincides with conventional matrix product. So STP is a general form of matrix product. Throughout this paper, the matrix product is assumed to be STP, and the symbol “⋉” is omitted if there is no confusion.Definition 3 (see [19]).
A swap matrixW[m,n] is an mn×mn matrix, defined as follows: label its columns by (11,12,…,1n,…,m1,m2,…,mn); label its rows by (11,21,…,m1,…,1n,2n,…,mn), and then the element at the position [(I,J),(i,j)] is
(3)w(I,J),(i,j)=δi,jI,J={1,I=i,J=j,0,otherwise.Definition 4 (see [32]).
LetA=(aij), B=(bij)∈ℳm×n. The Hadamard product of A and B is defined as
(4)A⊙B=(aijbij)∈ℳm×n.Lemma 5 (see [19]).
(
1
) Let X∈ℛm and Y∈ℛn be two column vectors. Then,
(5)W[m,n]XY=YX.
(
2
) Given A∈ℳm×n, let Z∈ℛt be a column vector. Then,
(6)ZA=W[m,t]AW[t,n]Z=(It⊗A)Z.
(
3
) Let X∈ℛn, Y∈ℛq be two column vectors and let A∈ℳm×n, B∈ℳp×q be two given matrices. Then,
(7)(AX)⋉(BY)=(A⊗B)(X⋉Y).
(
4
) Let f(x1,x2,…,xr) be a Boolean function. Then, there exists a unique logical matrix Lf∈ℒ2×2r such that
(8)f(x1,x2,…,xr)=Lf⋉i=1rxi.
Here, Lf∈ℒ2×2r is called the structure matrix of f.Now, some structure matrices of basic logical operators are given as follows:(9)M∨∶=Md=δ2[1112];M∧∶=Mc=δ2[1222];M¬∶=Mn=δ2[21];M→∶=Mi=δ2[1211].
And the power reducing matrix is defined as
(10)Mr=δ4[14].
Then, if X,Y∈Δ, we will have X∨Y=MdXY, X∧Y=McXY, ¬X=MnX, X→Y=MiXY, and X⋉X=MrX.Definition 6 (see [33]).
LetV={v1,v2,…,vn} be a finite set, and let ℰ={E1,E2,…,Em} be a family of subsets of V; that is, Ej⊆V, j=1,2,…,m. The family ℰ is said to be a hypergraph on V denoted by H=(V,ℰ), if Ej≠⌀, j=1,2,…,m, and ⋃j=1mEj=V. The elements v1,v2,…,vn are called the vertices (hypervertices) and the sets E1,E2,…,Em are called the edges (hyperedges).The incidence matrix of hypergraphH=(V,ℰ) is a matrix A=(aij) with m rows that represent the edges of H and n columns that represent the vertices of H, such that
(11)aij={1,vj∈Ei,0,vj∉Ei.Definition 7 (see [33]).
Given a hypergraphH=(V,ℰ), a set S⊆V is called a stable set if it contains no edge Ei with |Ei|>1. Furthermore, S is called a maximum stable set, if any vertex subset strictly containing S is not a stable set. A stable set S is called an absolutely maximum stable set if |S| is the largest among all of the stable sets of H. The stable number of H, denoted by α(H), is defined to be the maximum cardinality of all the stable sets of H.Remark 8.
For a hypergraphH=(V,ℰ), any subset of stable set S is a stable set. If there exists Ei∈ℰ satisfying |Ei|=1, that is, H has an edge formed by an isolated vertex, then, all the stable sets of H can be obtained from all the stable sets of H′=(V′,ℰ′) where ℰ′=ℰ-{Ei}. In fact, if all the stable sets of H′ are S1,…,Sr, then, all the stable sets of H are S1,…,Sr,S1∪{Ei},…,Sr∪{Ei}. Therefore, in this paper, we just consider the edges of cardinality more than one. Additionally, the empty set ⌀ is regarded as a stable set of any hypergraph.Definition 9 (see [33]).
Aq-coloring is defined to be a partition of V into q stable sets S1,S2,…,Sq, each corresponding to a color. A hypergraph for which there exists a q-coloring is said to be q-colorable.


## 3. Stable Set Problem

In the section, we investigate the stable set problem of hypergraphs using the STP method and present algebraic equivalent conditions, as well as an algorithm.Given a hypergraphH=(V,ℰ) with n vertices V={v1,v2,…,vn} and m edges ℰ={E1,E2,…,Em}, assume that the incidence matrix of H is A=(aij)m×n. Denote the ith row of A by ai, i=1,2,…,m; then A=[a1T,a2T,…,amT]T. Assume that S is a subset of V. Then, in the following, we will discuss under what conditions the subset S is a stable set. First, we define some vectors.The CLV ofS, denoted by VS=[x1,x2,…,xn], is denoted as
(12)xi={1,vi∈S,0,vi∉S.
And then denote
(13)yij=[aij1-aij],yj=[xj1-xj],i=1,2,…,m,j=1,2,…,n.
It is easy to see that VS is a Boolean vector and yij,yj∈Δ. Then, we can present the following results.Theorem 10.
Consider the hypergraphH=(V,ℰ) expressed as above. Then S is a stable set of H if and only if the last row of matrix M¯ has at least one zero element, where
(14)M¯=(⨂nj=1⁡M)(⋉k=1n-1(I2k⊗W[2,2k]))(∑l=1m‍Yl),M=MnMi(I2⊗Mc)Mr,Yl=⋉t=1nylt.Proof.
LetE-l=El∖S with the CLV a¯l=[a¯l1,a¯l2,…,a¯ln], l=1,2,…,m. Denote
(15)y¯lt=[a¯lt1-a¯lt],l=1,2,…,m,t=1,2,…,n.
Then, S is a stable set if and only if, for every l∈{1,2,…,m},E¯l≠⌀; that is, a¯l≠01×n. Since a¯l≠01×n if and only if ⋉t=1ny¯lt≠δ2n2n if and only if the last element of ⋉t=1ny¯lt is 0, we just need to prove that, for every l∈{1,2,…,m}, the last element of ⋉t=1ny¯lt is 0 if and only if the last row of matrix M¯ has one zero component at least.
LetJ1T=δ2n2n. If, for every l∈{1,2,…,m}, the last element of ⋉t=1ny¯lt is 0, then, we get, for every l,J1⋉t=1ny¯lt=0. Thus, y¯lt satisfies
(16)J1∑l=1m‍⋉t=1ny¯lt=0.
Since E-l=El∖S, a¯lt=alt-alt∧xt. Hence,
(17)y¯lt=ylt-ylt∧yt=¬(ylt⟶(ylt∧yt))=MnMiyltMcyltyt=MnMi(I2⊗Mc)Mryltyt≜Myltyt.
So (16) can be expressed as
(18)J1∑l=1m‍⋉t=1nMyltyt=0.
By Lemma 5, we have
(19)⋉t=1nMyltyt=(⨂nj=1⁡M)(⋉t=1nyltyt),⋉t=1nyltyt=yl1y1yl2y2⋯ylnyn=yl1W[2,2]yl2y1y2⋯ylnyn=(I2⊗W[2,2])yl1yl2y1y2⋯ylnyn=⋯=⋉k=1n-1(I2k⊗W[2,2k])YlY,
where Y=⋉t=1nyt∈Δ2n and Yl is described in (14). Therefore, (16) becomes
(20)J1∑l=1m‍(⨂nj=1⁡M)⋉k=1n-1(I2k⊗W[2,2k])YlY=0.
That is,
(21)J1M¯Y=0.
Noticing that Y∈Δ2n, we have that (21) having a solution Y is equivalent to the last row of M¯ having one zero element at least. The necessity is proved.
On the other hand, if the last row ofM¯ has one zero element at least, then the equation J1M¯Y=0 has a solution Y∈Δ2n. Equivalently, (16) holds. Noticing that J1⋉t=1ny¯lt≥0, from (16) we obtain J1⋉t=1ny¯lt=0; that is, for every l∈{1,2,…,m}, the last element of ⋉t=1ny¯lt is 0. Hence the proof is completed.From the above theorem, we find that (21) plays an important role to calculate all the stable sets of hypergraph H. The following corollary shows the relationship between (21) and the stable sets of hypergraphs.Corollary 11.
Consider the hypergraphH in Theorem 10. H has a stable set if and only if (21) has a solution Y=⋉t=1nyt∈Δ2n. In addition, the number of stable sets of H is the cardinal of solution set of (21).In order to obtain all the stable sets of any hypergraph, we will give an algorithm according to the proof of Theorem10 and the results of Corollary 11.Algorithm 12.
Consider a hypergraphH shown in Theorem 10. The following steps are given to find all the stable sets of H. (1)
Calculate the matrixM¯ given in (14).(2)
Denote the last row ofM¯ by β=[b1,b2,…,b2n]. If bi≠0, for every i∈{1,2,…,2n}, then, H has no stable set and stop. Otherwise, find out all the zero elements of β: bi1=bi2=⋯=bip=0. Then, bik=0 corresponds to a solution, Y=δ2nik, of (21) and so does a stable set of H.(3)
From⋉j=1nyj=δ2nik, we can retrieve yt as yt=Stn⋉j=1nyj=Stnδ2nik, t=1,2,…,n, where Stn, t=1,2,…,n are defined as follows [19]:
(12)S1n=δ2[1⋯1︸2n-12⋯2︸2n-1],S2n=δ2[1⋯1︸2n-22⋯2︸2n-21⋯1︸2n-22⋯2︸2n-2],⋮Snn=δ2[12︸2⋯12︸2︸2n-1].
By the definition of (12), we obtain the stable set corresponding to δ2nik:
(23)S(ik)={vt∣yt=δ21,1≤t≤n}.
Thus, all the stable sets of H are {S(ik)∣k=1,2,…,p}.Remark 13.
From Algorithm12, we can obtain all the stable sets of hypergraph H; therefore, the absolutely maximum stable sets can also be determined. Denote the stable number of H by α0; then, α0=max1≤k≤p{|S(ik)|}, and all the absolutely maximum stable sets can be derived as S={S(ik)∣|S(ik)|=α0}.Remark 14.
Although the calculation of the above algorithm is complex, the advantage of this approach is that we can obtain all the stable sets as well as all the absolutely maximum stable sets of a hypergraph. And we can turn to the computer using MATLAB toolbox.Example 15.
Consider the hypergraphH=(V,ℰ), where V={v1,v2,v3,v4,v5}, ℰ={E1,E2,E3,E4}, E1={v1,v2,v3}, E2={v3,v4,v5}, E3={v2,v3,v4}, and E4={v2,v4,v5}. In the following, we use Algorithm 12 to find all the stable sets of the hypergraph.
By the definition of the incidence matrix of the hypergraphH, the incidence matrix of H is
(24)A=[11100001110111001011].
By MATLAB toolbox, we easily get
(25)M=[01001011],Y1=δ254,Y2=δ2525,Y3=δ2518,Y4=δ2521.
Thus,
(26)∑l=14‍Yl=δ254+δ2525+δ2518+δ2521=[00010000000000000=100100010000000]T.
Then, we obtain the last row of M¯ as
(27)β=[42111000100000003100100010000000],
and the indexes of zero elements in β are
(28)P={ik∣β(ik)=0}={6,7,8,10,11,12,13,14,15,16,19,20,22,23,24,26,27,28,29,30,31,32}.
For each index ik∈P, let ⋉i=15yi=δ25ik. Via computing yi=Si5δ25ik, i=1,2,…,5, we have all the stable sets of H as follows:
(29)i1=6~(x1,x2,x3,x4,x5)=(1,1,0,1,0)~S1={v1,v2,v4},i2=7~(x1,x2,x3,x4,x5)=(1,1,0,0,1)~S2={v1,v2,v5},i3=8~(x1,x2,x3,x4,x5)=(1,1,0,0,0)~S3={v1,v2},i4=10~(x1,x2,x3,x4,x5)=(1,0,1,1,0)~S4={v1,v3,v4},i5=11~(x1,x2,x3,x4,x5)=(1,0,1,0,1)~S5={v1,v3,v5},i6=12~(x1,x2,x3,x4,x5)=(1,0,1,0,0)~S6={v1,v3},i7=13~(x1,x2,x3,x4,x5)=(1,0,0,1,1)~S7={v1,v4,v5},i8=14~(x1,x2,x3,x4,x5)=(1,0,0,1,0)~S8={v1,v4},i9=15~(x1,x2,x3,x4,x5)=(1,0,0,0,1)~S9={v1,v5},i10=16~(x1,x2,x3,x4,x5)=(1,0,0,0,0)~S10={v1},i11=19~(x1,x2,x3,x4,x5)=(0,1,1,0,1)~S11={v2,v3,v5},i12=20~(x1,x2,x3,x4,x5)=(0,1,1,0,0)~S12={v2,v3},i13=22~(x1,x2,x3,x4,x5)=(0,1,0,1,0)~S13={v2,v4},i14=23~(x1,x2,x3,x4,x5)=(0,1,0,0,1)~S14={v2,v5},i15=24~(x1,x2,x3,x4,x5)=(0,1,0,0,0)~S15={v2},i16=26~(x1,x2,x3,x4,x5)=(0,0,1,1,0)~S16={v3,v4},i17=27~(x1,x2,x3,x4,x5)=(0,0,1,0,1)~S17={v3,v5},i18=28~(x1,x2,x3,x4,x5)=(0,0,1,0,0)~S18={v3},i19=29~(x1,x2,x3,x4,x5)=(0,0,0,1,1)~S19={v4,v5},i20=30~(x1,x2,x3,x4,x5)=(0,0,0,1,0)~S20={v4},i21=31~(x1,x2,x3,x4,x5)=(0,0,0,0,1)~S21={v5},i22=32~(x1,x2,x3,x4,x5)=(0,0,0,0,0)~S22=⌀.
Therefore, from the calculation results, we knowmaxik{|Sik|}=3; all the absolutely maximum stable sets are {S1,S2,S4,S5,S7,S11}.


## 4. Coloring Problem

In this section, we study the vertex coloring problem of hypergraphs, that is, givenq colors, how to color the vertices of the hypergraph H such that no edge has all its vertices with the same color.Consider a hypergraphH=(V,ℰ), with V={v1,v2,…,vn}, ℰ={E1,E2,…,Em}, and assume that its incidence matrix is A=(aij)∈ℬm×n. Given q kinds of colors: c1,c2,…,cq, let N={c1,c2,…,cq} be the color set; then, we can define a mapping ϕ:V↦N. Since all of the q colors may not be used, ϕ may not be a surjective. To solve the coloring problem of hypergraph H, we can just find a mapping ϕ satisfying that, for every edge Ek, there are two different vertices vs,vt∈Ek satisfying ϕ(vs)≠ϕ(vt).If the color problem is solvable, then each vertex inV has been colored by one of the colors. Thus, for given q colors, we can define a CLV xt=δqs∈Δq corresponding to the vertex vt∈V with the color cs; that is, ϕ(vt)=cs. Before investigating the coloring problem of H, we first calculate the structure matrix of the q valued function xs⊙xt for xs,xt∈Δq.Similar to (12), the q valued retrievers can be given as [19](30)S1,qn=δq[1⋯1︸qn-12⋯2︸qn-1⋯q⋯q︸qn-1],S2,qn=δq[1⋯1︸qn-22⋯2︸qn-2⋯q⋯q︸qn-2⋯1⋯1︸qn-22⋯2︸qn-2⋯q⋯q︸qn-2︸q],⋮Sn,qn=δq[12⋯q︸⋯12⋯q︸︸qn-1],and then, xs=Ss,qn⋉i=1nxi and xt=St,qn⋉i=1nxi. Let Mr,qn=Diag{δqn1,δqn2,…,δqnqn} and Hq=Diag{e1,e2,…,eq}, where ei=(δqi)T. With simple calculation, we have
(31)xs⊙xt=Hqxs⋉xt=HqSs,qn(⋉i=1nxi)St,qn(⋉i=1nxi)=HqSs,qn(Iqn⊗St,qn)Mr,qn(⋉i=1nxi).Define the structure matrix of⊙ by
(32)MstH=HqSs,qn(Iqn⊗St,qn)Mr,qn.
Next, we give the following algebraic condition of coloring problem of hypergraph H.Theorem 16.
The coloring problem is solvable if and only if there existsj∈{1,2,…,qn} such that
(33)Colj(M)≪b,
where
(34)b=∑s=1n-1‍∑t=s+1n‍[a1sa1ta2sa2t⋮amsamt],M=∑s=1n-1‍∑t=s+1n‍[a1sa1ta2sa2t⋮amsamt]J2MstH,J2=[1,1,…,1]q, and MstH, a structure matrix of ⊙, is HqSs,qn(Iqn⊗St,qn)Mr,qn by (31).Proof.
(Necessity) If the coloring problem is solvable, then, for every edgeEk∈ℰ, there exist two different vertices vs,vt in Ek such that ϕ(vs)≠ϕ(vt). That is, aks=akt=1 but xs≠xt. Then, for each k∈{1,2,…,m}, there exist s,t∈{1,2,…,n}, s≠t, satisfying aks=akt=1 but xs≠xt, which implies J2xs⊙xt=0<1. Thus,
(35)∑s=1n-1‍∑t=s+1n‍aksaktJ2xs⊙xt<∑s=1n-1‍∑t=s+1n‍aksakt.
By (31), we have
(36)∑s=1n-1‍∑t=s+1n‍aksaktJ2MstH(⋉i=1nxi)<∑s=1n-1‍∑t=s+1n‍aksakt,∀k∈{1,2,…,m}.
Equivalently,
(37)MY≪b,
where Y=⋉i=1nxi. Considering that Y=⋉i=1nxi∈Δqn, from the inequality (37), we know that there exists j∈{1,2,…,qn} such that Colj(M)≪b.
(Sufficiency) Assume that there existsj∈{1,2,…,qn} such that Colj(M)≪b. Then the inequality (37) has a solution Y∈Δqn. Thus, for every k∈{1,2,…,m}, the inequality (35) holds. Noticing that 0≤J2xs⊙xt≤1, we get that, for each k∈{1,2,…,m}, there exist s,t∈{1,2,…,n},s≠t such that aks=akt=1 implies J2xs⊙xt=0<1. Hence, the proof is completed.Based on the algebraic equivalent condition of the coloring problem, we can construct an algorithm to find out all the coloring schemes and coloring partitions.Algorithm 17.
Consider the hypergraphH and let a color set N={c1,c2,…,cq}. Each vertex vt corresponds to a color and, thus, corresponds to a q valued CLV xt∈Δq. We give the following steps to calculate all the coloring schemes. (1)
Calculate the matricesM and b given in Theorem 16.(2)
Find if there existsj∈{1,2,…,qn} such that Colj(M)≪b. If not, the coloring problem with the q colors is not solvable, and stop. Otherwise, find out all the columns of M satisfying the inequality (33) and denote their indexes by the set
(38)Q={j∣Colj(M)≪b}.(3)
Let⋉l=1nxl=δqnj, for every j∈Q. By (30), we get xi=Si,qn(⋉l=1nxl)=Si,qnδqnj, i=1,2,…,n. Then, let
(39)Sc1j={vi∣xi=δq1,1≤i≤n},Sc2j={vi∣xi=δq2,1≤i≤n},⋮Scqj={vi∣xi=δqq,1≤i≤n},
where Sckj is the set of vertices colored by the kth color, k∈{1,2,…,q}. Then, there are |Q| kinds of coloring schemes corresponding to the elements in Q.With the result of Theorem16, we can easily obtain a corollary on Sckj,k∈{1,2,…,q}, j∈Q.Corollary 18.
Assume that there existsj∈{1,2,…,qn} such that Colj(M)≪b. Then, the following hold: (1)
for eachk∈{1,2,…,q}, Sckj defined in Algorithm 17 is a stable set of H,(2)
for eachj∈Q, {Sc1j,Sc2j,…,Scqj} is a partition of the vertices of H.Remark 19.
From Theorem16 and Corollary 18, we know that if the coloring problem is solvable with the given q colors, the hypergraph is q-colorable. On the other hand, given the q colors, the coloring schemes obtained in Algorithm 17 contain all the coloring schemes with the colors not more than q. Then, the chromatic number denoted by χ(H), which is the minimum number of colors being used, is χ(H)=minj∈Q{|Nj|}, where Nj={i∣Scij≠⌀,1≤i≤q}. Therefore, the minimum coloring partition is
(40){Sc1j0,Sc2j0,…,Scqj0}∖{Scij∣Scij=⌀},whereNj0=χ(H).


## 5. Application in Storing Problem

A company producesn kinds of chemicals which contain some products that cannot be put in the same storehouse. The problem is that how many storehouses are needed at least to store the n kinds of chemicals and how to assign them. In order to solve the problem, we denote the n kinds of chemicals by V={v1,v2,…,vn} and m kinds of circumstances by ℰ={E1,E2,…,Em} where the chemicals in Ei⊆V, i=1,2,…,m, cannot be put in the same storehouse. Immediately, we obtain a hypergraph H=(V,ℰ). Then some chemicals can be put in the same storehouse if and only if the vertices corresponding to the chemicals can be colored with the same color. Therefore, to assign these chemicals is equivalent to solve the coloring problem of H. Here, we will give the following numerical example to illustrate it.Example 20.
There are five kinds of chemicals denoted byV={v1,v2,v3,v4,v5} needed to be put into two storehouses. Let a hypergraph H have the vertex set as V. And we know that some dangerous thing will happen if the following combinations appear: {v1,v2,v3}, {v3,v4,v5}, {v2,v3,v4}, and {v2,v4,v5}. Then we consider that these combinations are edges of the hypergraph. Thus, the storing problem is equivalent to the hypergraph coloring problem with two different colors. Letting a two-color set N={c1=Red,c2=Blue}, by Algorithm 17, we can get all the coloring schemes.
The incidence matrix of the hypergraphH is as follows:
(41)A=[11100001110111001011].
By Theorem 16, using MATLAB toolbox, we easily obtain(42)b=[3333]T,M=[33331111111111111111111111113333311111133111111331111113311111133311111111111133331111111111113331113111111311133111311111131113].Then, the index set Q of j satisfying (33) is
(43)Q={j∣Colj(M)≪b}={6,7,10,11,13,14,19,20,22,23,26,27}.
For eachj∈Q, let ⋉i=15xi=δ25j. By computing xi=Si,25δ25j,i=1,2,…,5, we have
(44)j=6,δ256~[x1,x2,x3,x4,x5]=δ2[11010],j=7,δ257~[x1,x2,x3,x4,x5]=δ2[11001],j=10,δ2510~[x1,x2,x3,x4,x5]=δ2[10110],j=11,δ2511~[x1,x2,x3,x4,x5]=δ2[10101],j=13,δ2513~[x1,x2,x3,x4,x5]=δ2[10011],j=14,δ2514~[x1,x2,x3,x4,x5]=δ2[10010],j=19,δ2519~[x1,x2,x3,x4,x5]=δ2[01101],j=20,δ2520~[x1,x2,x3,x4,x5]=δ2[01100],j=22,δ2522~[x1,x2,x3,x4,x5]=δ2[01010],j=23,δ2523~[x1,x2,x3,x4,x5]=δ2[01001],j=26,δ2526~[x1,x2,x3,x4,x5]=δ2[00110],j=27,δ2527~[x1,x2,x3,x4,x5]=δ2[00101],
from which we obtain the following 12 coloring schemes:
(45)Scheme1:Sc16={v1,v2,v4}(Red),Sc28={v3,v5}(Blue);Scheme2:Sc17={v1,v2,v5}(Red),Sc28={v3,v4}(Blue);Scheme3:Sc110={v1,v3,v4}(Red),Sc28={v2,v5}(Blue);Scheme4:Sc111={v1,v3,v5}(Red),Sc28={v2,v4}(Blue);Scheme5:Sc113={v1,v3,v5}(Red),Sc28={v2,v4}(Blue);Scheme6:Sc114={v1,v4}(Red),Sc28={v2,v3,v5}(Blue);Scheme7:Sc119={v2,v3,v5}(Red),Sc28={v1,v4}(Blue);Scheme8:Sc120={v2,v3}(Red),Sc28={v1,v4,v5}(Blue);Scheme9:Sc122={v2,v4}(Red),Sc28={v1,v3,v5}(Blue);Scheme10:Sc123={v2,v5}(Red),Sc28={v1,v3,v4}(Blue);Scheme11:Sc126={v3,v4}(Red),Sc28={v1,v2,v5}(Blue);Scheme12:Sc127={v3,v5}(Red),Sc28={v1,v2,v4}(Blue).
Thus, there are totally 12 kinds of storing methods.


## 6. Conclusion

In this paper, the stable set and vertex coloring problems of hypergraphs have been revised. Several new results and algorithms have been presented via a method of STP. By defining the incidence matrix of hypergraph and CLV of a vertex subset, one equivalent condition has been established for hypergraph stable set. And a new algorithm to find out all the stable sets and all the absolutely maximum stable sets has been obtained. Furthermore, we have considered the vertex coloring problem and got a necessary and sufficient condition in the form of algebraic inequality, by which an algorithm has been derived to search all the coloring schemes and minimum coloring partitions with the givenq colors for any hypergraph. Finally, the illustrative example and the application to storing problem have shown that the results presented in this paper are very effective. In papers [34, 35], the scheduling jobs can induce a mixed graph coloring, not a hypergraph coloring. Thus, the mixed graph coloring problem will be interesting to be discussed by STP in the future.



---

*Source: 783784-2014-04-28.xml*