Electronic Journal of Graph Theory and Applications 13 .
, 117Ae121 Bounds on ErdoUs - Faber - LovaAsz conjecture the uniform and regular cases Suresh M.
Hegdea .
Suresh Darab,c Department of Mathematical and Computational Sciences.
National Institute of Technology Karnataka.
Surathkal.
Mangalore.
India b VIT Bhopal University.
Kothri Kalan.
Sehore 466114.
India c The Institute of Mathematical Sciences.
HBNI.
Chennai.
India smhegde@nitk.
in, suresh.
dara@gmail.
Abstract We consider the ErdoUs - Faber - LovaAsz (EFL) conjecture for hypergraphs.
This paper gives an upper bound for the chromatic number of r regular linear hypergraphs H of size n.
If r Ou 4.
N(H) O 1.
181n and if r = 3.
N(H) O 1.
Keywords: hypergraphs, chromatic number.
ErdoUs - Faber - LovaAsz conjecture Mathematics Subject Classification : 05C15 DOI: 10.
5614/ejgta.
Introduction A hypergraph is a structure H = (V, (Ei : i OO I)) where the vertex set V is an arbitrary set, and every Ei OI V .
These sets Ei are called the hyperedges of the hypergraph.
The degree of a vertex v in H is the number of edges d.
containing v.
The rank of an edge E is the cardinality r.
of e.
A hypergraph is said to be linear if no two hyperedges have more than one vertex in common.
A hypergraph is said to be uniform if all of its hyperedges have the same If the degree of each vertex is same then the hypergraph is called regular.
The dual hypergraph HO of a hypergraph H is the transpose of an incident matrix of the hypergraph H.
Clearly the edges of HO are the vertices of H and vice versa, ranks swap with degrees.
Received: 1 October 2019.
Revised: 8 March 2025.
Accepted: 21 March 2025.
Bounds on EFL conjecture - the uniform and regular cases Hegde and S.
Dara The dual of a uniform hypergraph is regular and vice versa.
It is easy to see that H is linear if and only if HO is linear.
A coloring of a hypergraph is an assignment of colors to the vertices so that no two vertices of an edge have the same color.
A k-coloring of a hypergraph is a coloring of it where the number of used colors is at most k .
The chromatic number N(H) of a hypergraph is the least number of colors needed to color the vertices of hypergraph H so that no two vertices of an edge have the same color.
The chromatic index q(H) .
r edge chromatic numbe.
of a hypergraph is the least number of colors needed to color the edges of hypergraph H so that no two intersecting edges have the same color .
In 1972.
ErdoUs - Faber - LovaAsz (EFL) conjectured .
as follows:
Conjecture 1.
If H is a linear hypergraph consisting of n edges of cardinality n, then it is possible to color the vertices with n colors so that no two vertices with the same color are in the same edge.
Conjecture 2.
Let H be a linear hypergraph with n vertices and no rank 1 edges.
Then q(H) O n .
Chang and Lawler .
presented a simple proof that the edges of a simple hypergraph on n vertices can be colored with at most .
Kahn .
showed that the chromatic number of H is at most n o.
Faber .
proves that for fixed degree, there can be only finitely many counterexamples to EFL on this class of regular and uniform hypergraphs.
In this paper we are using the dual graph version of the Conjecture 2, we gave an upper bound for the chromatic number of r regular linear hypergraphs H of size n.
If r Ou 4.
N(H) O 1.
and if r = 3.
N(H) O 1.
Results Theorem 2.
Let H be a linear hypergraph of size n.
If H is r regular .
Ou .
then N(H) O 1.
If H is 3 regular then N(H) O 1.
Proof.
Let H = (V.
E) be a linear hypergraph of size n and H is r regular .
Ou .
Let E1 .
E2 , .
En be the edges of H.
Since H is r regular and |E| = n, for every Ei OO E, |Ei | O nOe1 O nOe1 = N .
Let C = .
, 2, 3, .
, .
be the set of , then |V | O n.
Oe.
O n3 nOe1 rOe1 r.
Oe.
rOe1 available colors.
Since degree of each vertex is r, for every vertex vi OO V , there exists r edges Ei1 .
Ei2 , .
Eir which are incident at the vertex vi .
For i = 1 to N Step 1.
Color vi with smallest color not already seen in Oj Eij .
If no such color exist go to Step 2.
Bounds on EFL conjecture - the uniform and regular cases Hegde and S.
Dara Step 2.
find a color c such that OA vk OO Oj Eij with col.
k ) = c .
t most r such vk ) OE colors ck OO colors assigned to Oj=1,2,.
,r Ekj .
Recolor each such vk with ck and color vi with c.
If no such c found, abort the process.
Claim: For sufficiently large.
Ou 1, procedure dose not abort.
Suppose procedure aborts at vi .
That means all n colors seen in Oj Eij \ .
i } at vertices that cannot be recolored.
Pick one such vertex for each color, set S.
|S| = n.
For vertices v OO S, v sees all n colors.
At most |Eij | of these are seen in the edge EIj OU v.
The rest are seen outside Eij .
v places a token on each vertex it sees colored with a color not in Eij .
v places Ou n Oe |Eij | tokens.
So total number of tokens places Ou |S|.
Oe |Eij |) Ou n.
Oe nOe1 rOe1 How many tokens can be placed on a single vertex u? A If u OO Oj EIj , then say u OO Ei1 .
By H is r regular, u belongs to rOe1 other edges E1A .
E2A , .
ErOe1 By linearity property, at most one vertex each on Ei2 .
Ei3 , .
Eir lies on E1A , and same for E2A and so on.
So, at most .
Oe .
2 vertices of S can place a token on u.
If u OO / Oj EIj , then col.
is seen in S, say on S O Ei1 .
then no vertex in S O Ei1 will place a token on u.
The r edges through u intersects Ei2 .
Ei3 , .
Eir in at most one vertex.
So, there are at most r.
Oe .
vertices of S can place a token on u.
Therefore number of token per vertex is at most r.
Oe .
|S|.
inimum number of token placed by v OO S) O .
umber of toke.
O .
umber of vertice.
umber of tokens per verte.
Oe .
|S|.
Oe |EIj |) O .
umber of token.
O nr nOe1 rOe1 nOe1 nOe1 n.
Oe rOe1 ) O n rOe1 .
Oe .
n Oe nOe1 ) O n( nOe1 .
Oe .
) rOe1 rOe1 nOe1 nOe1 ( n Oe rOe1 ) O ( rOe1 .
Oe .
) 2 n Oe nOe1 Oe .
Oe .
nOe1 O 0.
rOe1 rOe1 nOe1 Let A = rOe1 , then the above inequality is 2 n Oe A Oe .
Oe .
A O 0.
Oo AA A2 4.
Oe.
An Consider n Oe A Oe .
Oe .
A = P (), then the zeros are P .
= Oe.
Oe Oo A A2 4.
Oe.
An .
A < 0, so for all > = .
P () > 0.
Choosing so that > , we conclude that with n colors the procedure successfully colors The value Oo of :
nOe1 A A2 4.
Oe.
An = O rOe1
= nB, where B = rOe1
rOe1
O nB Oo n2nB 4n
= B 2B 4
Case 1.
OoIf r Ou 4.
O B 2B 4 O 1.
180460 A A A < 1.
181 (B = rOe1 Then for every > .
N(H) O n.
Therefore N(H) O 1.
Case 2.
OoIf r = 3
O B 2B 4
Bounds on EFL conjecture - the uniform and regular cases = 41 Hegde and S.
Dara
(B = rOe1
= 12 )
Oo = 1.
= 1.
0307764 A A A 0.
25 < 1.
Therefore N(H) O 1.
From the above theorem one can observe that the upper bound of chromaticOo number of r regular linear hypergraphs H of size n is depends on the value of , where O B 2B 4 (B = rOe1 Clearly as r increases the value of will decrease.
Therefore if r Ou 5, then the upper bound of N(H) is even smaller than 1.
Theorem 2.
Let H be a linear uniform hypergraph of size n.
If OI(H) Ou n2 then N(H) O 1.
Proof.
Let H = (V, {E1 .
E2 , .
En }) be a linear uniform hypergraph of size n and OI(H) Ou n2 .
Let v be a maximum degree .
= m and v is incident with the edges E1 .
E2 , .
Em .
nOe1vertex, any Ei there are at most dOe1 vertices of degree d.
Arrange the vertices of H in non increasing order of degree.
We will color the vertices in this order, using .
Assume we next color a vertex v of degree k Ou 4.
At this point only vertices of degree k or greater have been Oe1 assigned colors.
At this stage in each edge incident with vertex v there are at most nOe1 kOe1 nOe1 vertices have been colored, which implies there are at most k kOe1 Oe 1 < .
colors are used to the vertices incident to the edges which are incident to v.
That means there will be an unused color for v.
For vertices of degree 4, 3 and 2 we apply the following method.
Partition the vertices of degree d into two sets Ad and Bd , where Ad be the set of all degree d vertices which are not incident with any of the edges E1 .
E2 , .
Em and Bd be the remaining degree djvertices.
kFirst assign the colors to the vertics are in Ad , at this stage in any edge there are Oe 1 vertices have been colored for d = 4, 3, 2.
Therefore always there is a free at most dOe1 color for assigning to the vertices ofjAd .
For dk = 4, 3, while assigning colors to the vertix u from Oe dOe1 Oe 1 < .
vertices have been colored.
Therefore Bd , there are .
Oe .
nOe1 dOe1 always there is a free color for assigning to the vertices of Bd .
For d = 2, let u OO B2 be the vertex we have to color.
Let u OO Ei .
Ej for some i, j, then the vertex v is in either Ei or Ej but not both.
Assume v is in Ei , then in Ei there are at most n2 Oe 1 vertices have been colored, that means there are at least 3n 1 colors are free from Ei .
Ej has at most n Oe 2 vertices have been colored and it has at least n4 2 colors free from Ej .
Let X be the set of free colors from Ei and Y be the set of free colors from Ej .
If Ei O Ej = OI there is a free color to assign to the vertex u.
If not, there exist two degree two vertices p, q such that p OO Ei , q OO Ej and p, q OO Ek for some k and color of p in Y , color of q in X.
Sincethe sum of number of free colors from Ei and number of free colors from Ej is > n and the number of vertices in Ek is at most n Oe 1, we can make either color of p or color q be free and this color to be assigned to u.
if such Ek is not available then the number of vertices colored in Ei O Ej < 1.
Corollary 2.
Let H be a linear uniform hypergraph of size n.
If H has at least n2 independent edges then N(H) O 1.
Bounds on EFL conjecture - the uniform and regular cases Hegde and S.
Dara Acknowledgement Part of this work was done when the second author was a postdoc at the Institute of Mathematical Sciences (IMS.
Chennai.
Also, authors would like to thank Dr.
Meena Mahajan.
IMSc.
Chennai for her valuable suggestions.
References