Abstract | ||
---|---|---|
Erdźs, Faber and Lovász conjectured in 1972 that the vertices of a linear hypergraph with n edges, each of size n, can be strongly colored with n colors. It was shown by Romero and Sánchez-Arroyo that an equivalent conjecture is obtained when linear hypergraphs are replaced by n-clusters. In this paper we describe new families of EFL-compliant n-clusters; that is, those for which the conjecture holds. Moreover, we describe ways to extend some n-clusters to larger ones preserving EFL-compliance. Also, our approach allowed us to provide a new upper bound for the chromatic number of n-clusters. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1007/s00373-016-1733-8 | Graphs and Combinatorics |
Keywords | Field | DocType |
Linear hypergraph, n-Cluster, Strong vertex coloring, Chromatic number, Edge coloring, Chromatic index, 05C65, 05C15 | Discrete mathematics,Topology,Edge coloring,Combinatorics,Lovász conjecture,Fractional coloring,Vertex (geometry),Upper and lower bounds,Hypergraph,Constraint graph,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
32 | 6 | 1435-5914 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gilberto Calvillo | 1 | 0 | 0.34 |
David Romero | 2 | 22 | 3.65 |