Bounds on Erdos - Faber - Lov ˝ asz conjecture - ´ the uniform and regular cases

Suresh M. Hegde^a , Suresh Darab,c

^aDepartment of Mathematical and Computational Sciences, National Institute of Technology Karnataka, Surathkal, Mangalore, India

^bVIT Bhopal University, Kothri Kalan, Sehore 466114, India

^cThe Institute of Mathematical Sciences, HBNI, Chennai, India

smhegde@nitk.edu.in, suresh.dara@gmail.com

We consider the Erdos - Faber - Lov ˝ asz (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 ≥ 4, χ(H) ≤ 1.181n and if r = 3, χ(H) ≤ 1.281n.

Keywords: hypergraphs, chromatic number, Erdos - Faber - Lov ˝ asz conjecture ´

Mathematics Subject Classification : 05C15

DOI: 10.5614/ejgta.2025.13.1.8

1. Introduction

A hypergraph is a structure H = (V,(Eⁱ : i ∈ I)) where the vertex set V is an arbitrary set, and every Eⁱ ⊆ V . These sets Eⁱ are called the hyperedges of the hypergraph[11].

The degree of a vertex v in H is the number of edges d(v) containing v. The rank of an edge E is the cardinality r(e) 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 rank. If the degree of each vertex is same then the hypergraph is called regular.

The dual hypergraph H ∗ of a hypergraph H is the transpose of an incident matrix of the hypergraph H. Clearly the edges of H ∗ are the vertices of H and vice versa, ranks swap with degrees,

Received: 1 October 2019, Revised: 8 March 2025, Accepted: 21 March 2025.

etc. The dual of a uniform hypergraph is regular and vice versa. It is easy to see that \(\mathbf{H}\) is linear if and only if \(\mathbf{H}^*\) 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 [7] [8].

The chromatic number \(\chi(\mathbf{H})\) of a hypergraph is the least number of colors needed to color the vertices of hypergraph \(\mathbf{H}\) so that no two vertices of an edge have the same color.

The chromatic index \(q(\mathbf{H})\) (or edge chromatic number) of a hypergraph is the least number of colors needed to color the edges of hypergraph \(\mathbf{H}\) so that no two intersecting edges have the same color [10].

In 1972, Erdős - Faber - Lovász (EFL) conjectured [3] [4] 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[1].

Conjecture 2. Let \(\mathbf{H}\) be a linear hypergraph with n vertices and no rank 1 edges. Then \(q(\mathbf{H}) \leq n\) [6].

Chang and Lawler [2] presented a simple proof that the edges of a simple hypergraph on n vertices can be colored with at most [1.5n-2] colors. Kahn [9] showed that the chromatic number of H is at most n + o(n). Faber [5] 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 \(\mathbf{H}\) of size n. If \(r \geq 4\), \(\chi(\mathbf{H}) \leq 1.181n\) and if r = 3, \(\chi(\mathbf{H}) \leq 1.281n\).

2. Results

Theorem 2.1. Let H be a linear hypergraph of size n.

• 1. If H is r regular \((r \ge 4)\) then \(\chi(H) \le 1.181n\).
• 2. If H is 3 regular then \(\chi(H) \leq 1.281n\).

Proof. Let H=(V,E) be a linear hypergraph of size n and H is r regular \((r\geq 3)\). Let \(E_1,E_2,\ldots E_n\) be the edges of H. Since H is r regular and |E|=n, for every \(E_i\in E, |E_i|\leq \lfloor\frac{n-1}{r-1}\rfloor\leq\frac{n-1}{2}\), then \(|V|\leq\frac{n(n-1)}{r(r-1)}\leq\frac{n}{3}\lfloor\frac{n-1}{r-1}\rfloor=N(say)\). Let \(C=\{1,2,3,\ldots,\alpha n\}\) be the set of available colors. Since degree of each vertex is r, for every vertex \(v_i\in V\), there exists r edges \(E_{i_1},E_{i_2},\ldots E_{i_r}\) which are incident at the vertex \(v_i\).

For i = 1 to N

Step 1. Color \(v_i\) with smallest color not already seen in \(\bigcup_i E_{i_i}\). If no such color exist go to Step 2.

Step 2. find a color c such that \(\forall v_k \in \bigcup_j E_{i_j}\) with \(col(v_k) = c\) (at most r such \(v_k\)) \(\exists\) colors \(c_k \notin colors\) assigned to \(\bigcup_{j=1,2,\ldots,r} E_{k_j}\).

Recolor each such \(v_k\) with \(c_k\) and color \(v_i\) with c. If no such c found, abort the process.

Claim: For \(\alpha\) sufficiently large, \(\alpha \geq 1\), procedure dose not abort.

Suppose procedure aborts at \(v_i\). That means all \(\alpha n\) colors seen in \(\cup_j E_{i_j} \setminus \{v_i\}\) at vertices that cannot be recolored. Pick one such vertex for each color, set S. \(|S| = \alpha n\). For vertices \(v \in S\), v sees all \(\alpha n\) colors. At most \(|E_{i_j}|\) of these are seen in the edge \(E_{I_j} \ni v\). The rest are seen outside \(E_{i_j}\). v places a token on each vertex it sees colored with a color not in \(E_{i_j}\).

\(v \text{ places} \ge \alpha n - |E_{i_i}| \text{ tokens.}\)

So total number of tokens places \(\geq |S| \cdot (\alpha n - |E_{i_j}|) \geq \alpha n(\alpha n - \lfloor \frac{n-1}{r-1} \rfloor)\).

How many tokens can be placed on a single vertex u?

If \(u \in \bigcup_j E_{I_j}\), then say \(u \in E_{i_1}\). By H is r regular, u belongs to r-1 other edges \(E'_1, E'_2, \ldots, E'_{r-1}\). By linearity property, at most one vertex each on \(E_{i_2}, E_{i_3}, \ldots, E_{i_r}\) lies on \(E'_1\), and same for \(E'_2\) and so on. So, at most \((r-1)^2\) vertices of S can place a token on u.

If \(u \notin \bigcup_j E_{I_j}\), then col(u) is seen in S, say on \(S \cap E_{i_1}\). then no vertex in \(S \cap E_{i_1}\) will place a token on u. The r edges through u intersects \(E_{i_2}, E_{i_3}, \ldots, E_{i_r}\) in at most one vertex. So, there are at most r(r-1) vertices of S can place a token on u. Therefore number of token per vertex is at most r(r-1).

|S|. (minimum number of token placed by \(v \in S\)) \(\leq\) (number of token) \(\leq\) (number of vertices) (number of tokens per vertex)

\[|S|(\alpha n - |E_{I_j}|) \leq \text{(number of tokens)} \leq \frac{n}{r} \left\lfloor \frac{n-1}{r-1} \right\rfloor r(r-1)\] \[\alpha n(\alpha n - \left\lfloor \frac{n-1}{r-1} \right\rfloor) \leq n \left\lfloor \frac{n-1}{r-1} \right\rfloor (r-1)\] \[n(\alpha^2 n - \alpha \left\lfloor \frac{n-1}{r-1} \right\rfloor) \leq n \left( \left\lfloor \frac{n-1}{r-1} \right\rfloor (r-1) \right)\] \[(\alpha^2 n - \alpha \left\lfloor \frac{n-1}{r-1} \right\rfloor) \leq \left( \left\lfloor \frac{n-1}{r-1} \right\rfloor (r-1) \right)\] \[\alpha^2 n - \alpha \left\lfloor \frac{n-1}{r-1} \right\rfloor - (r-1) \left\lfloor \frac{n-1}{r-1} \right\rfloor \leq 0.\]

Let \(A = \left\lfloor \frac{n-1}{r-1} \right\rfloor\), then the above inequality is \(\alpha^2 n - \alpha A - (r-1)A \le 0\).

Consider \(\alpha^2 n - \alpha A - (r-1)A = P(\alpha)\), then the zeros are \(\frac{A\pm\sqrt{A^2+4(r-1)An}}{2n}\). P(0) = -(r-1)A < 0, so for all \(\alpha > \beta = \frac{A+\sqrt{A^2+4(r-1)An}}{2n}\), \(P(\alpha) > 0\).

Choosing \(\alpha\) so that \(\alpha > \beta\), we conclude that with \(\alpha n\) colors the procedure successfully colors V.

The value of \(\beta\): \(\beta = \frac{A + \sqrt{A^2 + 4(r-1)An}}{2n} \text{ where } A = \left\lfloor \frac{n-1}{r-1} \right\rfloor \leq \frac{n}{r-1} = nB, \text{ where } B = \frac{1}{r-1}.\) \(\leq \frac{nB + \sqrt{n^2B^2 + 4n^2}}{\frac{2n}{2}} = \frac{B + \sqrt{B^2 + 4}}{2}\) \(\mathbf{Case 1. If } r \geq 4.\) \(\beta \leq \frac{B + \sqrt{B^2 + 4}}{2} \leq 1.180460 \cdots < 1.181 \quad (B = \frac{1}{r-1})\) Then for every \(\alpha > \beta\), \(\chi(H) \leq \alpha n\). Therefore \(\chi(H) \leq 1.181n\). \(\mathbf{Case 2. If } r = 3\) \(\beta \leq \frac{B + \sqrt{B^2 + 4}}{2}\)

\[\begin{split} &= \tfrac{1}{4} + \sqrt{\tfrac{1}{16} + 1} \quad (B = \tfrac{1}{r-1} = \tfrac{1}{2}) \\ &= \sqrt{\tfrac{17}{16}} + 0.25 \\ &= \sqrt{1.0625} + 0.25 \\ &= 1.0307764 \cdot \cdot \cdot + 0.25 < 1.281. \\ &\text{Therefore } \chi(H) \leq 1.281n. \end{split}\]

From the above theorem one can observe that the upper bound of chromatic number of r regular linear hypergraphs \({\bf H}\) of size n is depends on the value of \(\beta\), where \(\beta \leq \frac{B+\sqrt{B^2+4}}{2}\) \((B=\frac{1}{r-1})\). Clearly as r increases the value of \(\beta\) will decrease. Therefore if \(r \geq 5\), then the upper bound of \(\chi({\bf H})\) is even smaller than 1.181n.

Theorem 2.2. Let H be a linear uniform hypergraph of size n. If \(\Delta(H) \geq \frac{n}{2}\) then \(\chi(H) \leq 1.25n\).

Proof. Let \(H=(V, \{E_1, E_2, \dots E_n\})\) be a linear uniform hypergraph of size n and \(\Delta(H) \geq \frac{n}{2}\). Let v be a maximum degree vertex, \(\delta(v)=m\) and v is incident with the edges \(E_1, E_2, \dots E_m\). In any \(E_i\) there are at most \(\left\lfloor \frac{n-1}{d-1} \right\rfloor\) vertices of degree d. Arrange the vertices of H in non increasing order of degree. We will color the vertices in this order, using [1.25n] colors. Assume we next color a vertex v of degree \(k \geq 4\). At this point only vertices of degree k or greater have been assigned colors. At this stage in each edge incident with vertex v there are at most \(\left\lfloor \frac{n-1}{k-1} - 1 \right\rfloor\) vertices have been colored, which implies there are at most \(k \left\lfloor \frac{n-1}{k-1} - 1 \right\rfloor < [1.25n]\) 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 \(A_d\) and \(B_d\), where \(A_d\) be the set of all degree d vertices which are not incident with any of the edges \(E_1, E_2, \ldots, E_m\) and \(B_d\) be the remaining degree d vertices. First assign the colors to the vertics are in \(A_d\), at this stage in any edge there are at most \(\left| \frac{n/2}{d-1} - 1 \right|\) vertices have been colored for d = 4, 3, 2. Therefore always there is a free color for assigning to the vertices of \(A_d\). For d=4, 3, while assigning colors to the vertix u from \(B_d\), there are \((d-1)\left\lfloor \frac{n-1}{d-1}-1\right\rfloor+\left\lfloor \frac{n/2}{d-1}-1\right\rfloor<[1.25n]\) vertices have been colored. Therefore always there is a free color for assigning to the vertices of \(B_d\). For d=2, let \(u \in B_2\) be the vertex we have to color. Let \(u \in E_i, E_j\) for some i, j, then the vertex v is in either \(E_i\) or \(E_j\) but not both. Assume v is in \(E_i\), then in \(E_i\) there are at most \(\frac{n}{2}-1\) vertices have been colored, that means there are at least \(\frac{3n}{4} + 1\) colors are free from \(E_i\). \(E_j\) has at most n-2 vertices have been colored and it has at least \(\frac{n}{4} + 2\) colors free from \(E_j\). Let X be the set of free colors from \(E_i\) and Y be the set of free colors from \(E_i\). If \(E_i \cap E_j \neq \emptyset\) there is a free color to assign to the vertex u. If not, there exist two degree two vertices p, q such that \(p \in E_i\), \(q \in E_j\) and \(p, q \in E_k\) for some k and color of p in Y, color of q in X. Since the sum of number of free colors from \(E_i\) and number of free colors from \(E_i\) is > n and the number of vertices in \(E_k\) is at most n-1, we can make either color of por color q be free and this color to be assigned to u. if such \(E_k\) is not available then the number of vertices colored in \(E_i \cup E_j < 1.25n\).

Corollary 2.1. Let H be a linear uniform hypergraph of size n. If H has at least \(\frac{n}{2}\) independent edges then \(\chi(H) \leq 1.25n\).

Acknowledgement

Part of this work was done when the second author was a postdoc at the Institute of Mathematical Sciences (IMSc), Chennai. Also, authors would like to thank Dr. Meena Mahajan, IMSc, Chennai for her valuable suggestions.

References

• [1] C. Berge, On two conjectures to generalize Vizing's theorem, Matematiche (Catania), 45(1) (1990), 15–23.
• [2] W.I. Chang and E.L. Lawler, Edge coloring of hypergraphs and a conjecture of Erdos, Faber, ¨ Lovasz, ´ Combinatorica, 8(3) (1988), 293–295.
• [3] P. Erdos, Problems and results in graph theory and combinatorial analysis, ˝ Proc. British Combinatorial Conj., 5th, (1975), 169–192.
• [4] P. Erdos, On the combinatorial problems which I would most like to see solved, ˝ Combinatorica, 1 (1981), no. 1, 25–42.
• [5] V. Faber, The Erdos-Faber-Lov ˝ asz conjecture—the uniform regular case, ´ J. Comb., 1(2) (2010), 113–120.
• [6] V. Faber, Linear hypergraph edge coloring generalizations of the EFL conjecture, Bulletin of Mathematical Sciences and Applications, 17 (2016), 1–9.
• [7] S.M. Hegde and S. Dara, Further results on Erdos–Faber–Lov ˝ asz conjecture, ´ AKCE Int. J. Graphs Comb., 17(1) (2020), 614–631.
• [8] B. Jackson, G. Sethuraman, and C. Whitehead, A note on the Erdos-Farber-Lov ˝ asz conjec- ´ ture, Discrete Math., 307(7-8) (2007), 911–915.
• [9] J. Kahn, Coloring nearly-disjoint hypergraphs with n + o(n) colors, J. Combin. Theory Ser. A, 59(3) (1992), 31–39.
• [10] V. Paul and K.A. Germina, On edge coloring of hypergraphs and Erdos-Faber-Lov ¨ asz con- ´ jecture, Discrete Math. Algorithms Appl., 4(1) (2012), 1250003.
• [11] R. Zhang and F.M. Dong, Problems on chromatic polynomials of hypergraphs, Electron. J. Graph Theory Appl., 8(2) (2020), 241–246.