Skip to main content
exclude 1-edge hypergraph
Source Link

Let $H=(V,E)$ be a hypergraph. If $\kappa$ is a cardinal, we say that a map $c:E\to \kappa$ is an edge coloring if whenever $e_1,e_2\in E$ with $e_1\cap e_2\neq \emptyset$ then $c(e_1)\neq c(e_2)$. The smallest cardinal $\kappa$ such that there is an edge coloring $c:E\to \kappa$ is called the edge chromatic number of $H$, denoted by $\chi_e(H)$.

We say that $H=(V,E)$ is a dense linear hypergraph if

  1. $V \notin E$,
  2. $\bigcup E = V$,
  3. whenever $e_1\neq e_2 \in E$ then $|e_1\cap e_2| \leq 1$, and
  4. given $a\neq b\in V$ there is $e\in E$ with $\{a,b\}\in e$.

Given a positive integer $k$, is there a dense linear hypergraph $H= (V,E)$ with $V$ finite and $\chi_e(H) < 1/k\cdot |V|$?

Let $H=(V,E)$ be a hypergraph. If $\kappa$ is a cardinal, we say that a map $c:E\to \kappa$ is an edge coloring if whenever $e_1,e_2\in E$ with $e_1\cap e_2\neq \emptyset$ then $c(e_1)\neq c(e_2)$. The smallest cardinal $\kappa$ such that there is an edge coloring $c:E\to \kappa$ is called the edge chromatic number of $H$, denoted by $\chi_e(H)$.

We say that $H=(V,E)$ is a dense linear hypergraph if

  1. $\bigcup E = V$,
  2. whenever $e_1\neq e_2 \in E$ then $|e_1\cap e_2| \leq 1$, and
  3. given $a\neq b\in V$ there is $e\in E$ with $\{a,b\}\in e$.

Given a positive integer $k$, is there a dense linear hypergraph $H= (V,E)$ with $V$ finite and $\chi_e(H) < 1/k\cdot |V|$?

Let $H=(V,E)$ be a hypergraph. If $\kappa$ is a cardinal, we say that a map $c:E\to \kappa$ is an edge coloring if whenever $e_1,e_2\in E$ with $e_1\cap e_2\neq \emptyset$ then $c(e_1)\neq c(e_2)$. The smallest cardinal $\kappa$ such that there is an edge coloring $c:E\to \kappa$ is called the edge chromatic number of $H$, denoted by $\chi_e(H)$.

We say that $H=(V,E)$ is a dense linear hypergraph if

  1. $V \notin E$,
  2. $\bigcup E = V$,
  3. whenever $e_1\neq e_2 \in E$ then $|e_1\cap e_2| \leq 1$, and
  4. given $a\neq b\in V$ there is $e\in E$ with $\{a,b\}\in e$.

Given a positive integer $k$, is there a dense linear hypergraph $H= (V,E)$ with $V$ finite and $\chi_e(H) < 1/k\cdot |V|$?

Source Link

Edge coloring in dense linear hypergraphs

Let $H=(V,E)$ be a hypergraph. If $\kappa$ is a cardinal, we say that a map $c:E\to \kappa$ is an edge coloring if whenever $e_1,e_2\in E$ with $e_1\cap e_2\neq \emptyset$ then $c(e_1)\neq c(e_2)$. The smallest cardinal $\kappa$ such that there is an edge coloring $c:E\to \kappa$ is called the edge chromatic number of $H$, denoted by $\chi_e(H)$.

We say that $H=(V,E)$ is a dense linear hypergraph if

  1. $\bigcup E = V$,
  2. whenever $e_1\neq e_2 \in E$ then $|e_1\cap e_2| \leq 1$, and
  3. given $a\neq b\in V$ there is $e\in E$ with $\{a,b\}\in e$.

Given a positive integer $k$, is there a dense linear hypergraph $H= (V,E)$ with $V$ finite and $\chi_e(H) < 1/k\cdot |V|$?