Erdos–Faber–Lovász conjecture
Encyclopedia
In graph theory
, the Erdős–Faber–Lovász conjecture is an unsolved problem about graph coloring
, named after Paul Erdős
, Vance Faber
, and László Lovász
, who formulated it in 1972. It says:
A linear hypergraph is a hypergraph
with the property that every two hyperedges have at most one vertex in common. A hypergraph is said to be uniform if all of its hyperedges have the same number of vertices as each other. The cliques of size in the Erdős–Faber–Lovász conjecture may be interpreted as the hyperedges of an -uniform linear hypergraph that has the same vertices as the underlying graph. In this language, the Erdős–Faber–Lovász conjecture states that, given any -uniform linear hypergraph with hyperedges, one may -color the vertices such that each hyperedge has one vertex of each color.
A simple hypergraph is a hypergraph in which at most one hyperedge connects any pair of vertices and there are no hyperedges of size at most one. In the graph coloring formulation of the Erdős–Faber–Lovász conjecture, it is safe to remove vertices that belong to a single clique, as their coloring presents no difficulty; once this is done, the hypergraph that has a vertex for each clique, and a hyperedge for each graph vertex, forms a simple hypergraph.
And, the hypergraph dual of vertex coloring
is edge coloring
. Thus, the Erdős–Faber–Lovász conjecture is equivalent to the statement that any simple hypergraph with vertices has chromatic index (edge coloring number) at most .
The graph of the Erdős–Faber–Lovász conjecture may be represented as an intersection graph
of sets: to each vertex of the graph, correspond the set of the cliques containing that vertex, and connect any two vertices by an edge whenever their corresponding sets have a nonempty intersection. Using this description of the graph, the conjecture may be restated as follows: if some family of sets has total elements, and any two sets intersect in at most one element, then the intersection graph of the sets may be -colored.
The intersection number
of a graph is the minimum number of elements in a family of sets whose intersection graph is , or equivalently the minimum number of vertices in a hypergraph whose line graph is . define the linear intersection number of a graph, similarly, to be the minimum number of vertices in a linear hypergraph whose line graph is . As they observe, the Erdős–Faber–Lovász conjecture is equivalent to the statement that the chromatic number of any graph is at most equal to its linear intersection number.
present another yet equivalent formulation, in terms of the theory of clones
.
, Vance Faber
, and László Lovász
formulated the conjecture in 1972.
Paul Erdős
originally offered US$50 for proving the conjecture in the affirmative, and later raised the reward to US$500.
proved that the chromatic number of the graphs in the conjecture is at most , and improved this to .
A version of the conjecture that uses the fractional chromatic number
in place of the chromatic number is known to be true. That is, if a graph is formed as the union of -cliques that intersect pairwise in at most one vertex, then can be -colored.
In the framework of edge coloring simple hypergraphs, defines a number from a simple hypergraph as the number of hypergraph vertices that belong to a hyperedge of three or more vertices. He shows that, for any fixed value of , a finite calculation suffices to verify that the conjecture is true for all simple hypergraphs with that value of . Based on this idea, he shows that the conjecture is indeed true for all simple hypergraphs with . In the formulation of coloring graphs formed by unions of cliques, Hindman's result shows that the conjecture is true whenever at most ten of the cliques contain a vertex that belongs to three or more cliques. In particular, it is true for .
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the Erdős–Faber–Lovász conjecture is an unsolved problem about graph coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
, named after Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
, Vance Faber
Vance Faber
Vance Faber is a mathematician, known for his work in combinatorics, applied linear algebra and image processing....
, and László Lovász
László Lovász
László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
, who formulated it in 1972. It says:
- If complete graphComplete graphIn the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
s, each having exactly vertices, have the property that every pair of complete graphs has at most one shared vertex, then the union of the graphs can be colored with colors.
Equivalent formulations
introduced the problem with a story about seating assignment in committees: suppose that, in a university department, there are committees, each consisting of faculty members, and that all committees meet in the same room, which has chairs. Suppose also that at most one person belongs to the intersection of any two committees. Is it possible to assign the committee members to chairs in such a way that each member sits in the same chair for all the different committees to which he or she belongs? In this model of the problem, the faculty members correspond to graph vertices, committees correspond to complete graphs, and chairs correspond to vertex colors.A linear hypergraph is a hypergraph
Hypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
with the property that every two hyperedges have at most one vertex in common. A hypergraph is said to be uniform if all of its hyperedges have the same number of vertices as each other. The cliques of size in the Erdős–Faber–Lovász conjecture may be interpreted as the hyperedges of an -uniform linear hypergraph that has the same vertices as the underlying graph. In this language, the Erdős–Faber–Lovász conjecture states that, given any -uniform linear hypergraph with hyperedges, one may -color the vertices such that each hyperedge has one vertex of each color.
A simple hypergraph is a hypergraph in which at most one hyperedge connects any pair of vertices and there are no hyperedges of size at most one. In the graph coloring formulation of the Erdős–Faber–Lovász conjecture, it is safe to remove vertices that belong to a single clique, as their coloring presents no difficulty; once this is done, the hypergraph that has a vertex for each clique, and a hyperedge for each graph vertex, forms a simple hypergraph.
And, the hypergraph dual of vertex coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
is edge coloring
Edge coloring
In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several...
. Thus, the Erdős–Faber–Lovász conjecture is equivalent to the statement that any simple hypergraph with vertices has chromatic index (edge coloring number) at most .
The graph of the Erdős–Faber–Lovász conjecture may be represented as an intersection graph
Intersection graph
In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...
of sets: to each vertex of the graph, correspond the set of the cliques containing that vertex, and connect any two vertices by an edge whenever their corresponding sets have a nonempty intersection. Using this description of the graph, the conjecture may be restated as follows: if some family of sets has total elements, and any two sets intersect in at most one element, then the intersection graph of the sets may be -colored.
The intersection number
Intersection number
In mathematics, and especially in algebraic geometry, the intersection number generalizes the intuitive notion of counting the number of times two curves intersect to higher dimensions, multiple curves, and accounting properly for tangency...
of a graph is the minimum number of elements in a family of sets whose intersection graph is , or equivalently the minimum number of vertices in a hypergraph whose line graph is . define the linear intersection number of a graph, similarly, to be the minimum number of vertices in a linear hypergraph whose line graph is . As they observe, the Erdős–Faber–Lovász conjecture is equivalent to the statement that the chromatic number of any graph is at most equal to its linear intersection number.
present another yet equivalent formulation, in terms of the theory of clones
Clone (algebra)
In universal algebra, a clone is a set C of operations on a set A such that*C contains all the projections , defined by ,*C is closed under composition : if f, g1, …, gm are members of C such that f is m-ary, and gj is n-ary for every j, then the n-ary operation is in C.Given an algebra...
.
History and partial results
Paul ErdősPaul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
, Vance Faber
Vance Faber
Vance Faber is a mathematician, known for his work in combinatorics, applied linear algebra and image processing....
, and László Lovász
László Lovász
László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
formulated the conjecture in 1972.
Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
originally offered US$50 for proving the conjecture in the affirmative, and later raised the reward to US$500.
proved that the chromatic number of the graphs in the conjecture is at most , and improved this to .
Related problems
It is also of interest to consider the chromatic number of graphs formed as the union of cliques of vertices each, without restricting how big the intersections of pairs of cliques can be. In this case, the chromatic number of their union is at most , and some graphs formed in this way require this many colors.A version of the conjecture that uses the fractional chromatic number
Fractional coloring
Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. It is a generalization of ordinary graph coloring. In a traditional graph coloring, each vertex in a graph is assigned some color, and adjacent vertices — those connected by edges — must be assigned...
in place of the chromatic number is known to be true. That is, if a graph is formed as the union of -cliques that intersect pairwise in at most one vertex, then can be -colored.
In the framework of edge coloring simple hypergraphs, defines a number from a simple hypergraph as the number of hypergraph vertices that belong to a hyperedge of three or more vertices. He shows that, for any fixed value of , a finite calculation suffices to verify that the conjecture is true for all simple hypergraphs with that value of . Based on this idea, he shows that the conjecture is indeed true for all simple hypergraphs with . In the formulation of coloring graphs formed by unions of cliques, Hindman's result shows that the conjecture is true whenever at most ten of the cliques contain a vertex that belongs to three or more cliques. In particular, it is true for .