✦ LIBER ✦

On the Degree, Size, and Chromatic Index of a Uniform Hypergraph

✍ Scribed by Noga Alon; Jeong Han Kim

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 274 KB
Volume: 77
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1996.2728

No coin nor oath required. For personal study only.

✦ Synopsis

Let H be a k-uniform hypergraph in which no two edges share more than t common vertices, and let D denote the maximum degree of a vertex of H. We conjecture that for every =>0, if D is sufficiently large as a function of t, k, and =, then the chromatic index of H is at most (t&1+1Ât+=) D. We prove this conjecture for the special case of intersecting hypergraphs in the following stronger form: If H is an intersecting k-uniform hypergraph in which no two edges share more than t common vertices and D is the maximum degree of a vertex of H, where D is sufficiently large as a function of k, then H has at most (t&1+1Ât) D edges.

📜 SIMILAR VOLUMES

The Maximum Size of 3-Uniform Hypergraph

The Maximum Size of 3-Uniform Hypergraphs Not Containing a Fano Plane

✍ Dominique De Caen; Zoltán Füredi 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 73 KB

A conjecture of V. So s [3] is proved that any set of 3 4 ( n 3 )+cn 2 triples from an n-set, where c is a suitable absolute constant, must contain a copy of the Fano configuration (the projective plane of order two). This is an asymptotically sharp estimate.

A note on the line-distinguishing chroma

A note on the line-distinguishing chromatic number and the chromatic index of a graph

✍ N. Zagaglia Salvi 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

## Abstract Let λ(__G__) be the line‐distinguishing chromatic number and __x__′(__G__) the chromatic index of a graph __G__. We prove the relation λ(__G__) ≥ __x__′(__G__), conjectured by Harary and Plantholt. © 1993 John Wiley & Sons, Inc.

The size of edge chromatic critical grap

The size of edge chromatic critical graphs with maximum degree 6

✍ Rong Luo; Lianying Miao; Yue Zhao 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 216 KB 👁 1 views

## Abstract In 1968, Vizing [Uaspekhi Mat Nauk 23 (1968) 117–134; Russian Math Surveys 23 (1968), 125–142] conjectured that for any edge chromatic critical graph ${{G}} = ({{V}}, {{E}})$ with maximum degree $\Delta$, $|{{E}}| \geq {{{1}}\over {{2}}}\{(\Delta {{- 1}})|{{V}}| + {{3}}\}$. This conject

On the oriented chromatic index of orien

On the oriented chromatic index of oriented graphs

✍ Pascal Ochem; Alexandre Pinlou; Éric Sopena 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 227 KB

## Abstract A homomorphism from an oriented graph __G__ to an oriented graph __H__ is a mapping $\varphi$ from the set of vertices of __G__ to the set of vertices of __H__ such that $\buildrel {\longrightarrow}\over {\varphi (u) \varphi (v)}$ is an arc in __H__ whenever $\buildrel {\longrightarrow}

The Degree and Index of a Finite Group

✍ Yakov Berkovich 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 179 KB

A note concerning the chromatic index of

A note concerning the chromatic index of multigraphs

✍ A. J. W. Hilton; Bill Jackson 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 214 KB

We improve an upper bound for the chromatic index of a multigraph due to Andersen and Gol'dberg. As a corollary w e deduce that if no t w o edges of multiplicity at least t w o in G are adjacent, then ,y'(G) s A ( G ) + 1. In addition w e generalize results concerning the structure of critical graph