triangle free

Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★

Author(s): Kostochka; Reed

\begin{conjecture} A triangle-free graph with maximum degree $\Delta$ has chromatic number at most $\ceil{\frac{\Delta}{2}}+2$. % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords: chromatic number; girth; maximum degree; triangle free

Non-edges vs. feedback edge sets in digraphs ★★★

Author(s): Chudnovsky; Seymour; Sullivan

For any simple digraph $G$, we let $\gamma(G)$ be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and $\beta(G)$ be the size of the smallest \Def[feedback edge set]{feedback arc set}.

\begin{conjecture}If $G$ is a simple digraph without directed cycles of length $\le 3$, then $\beta(G) \le \frac{1}{2} \gamma(G)$. \end{conjecture}

Keywords: acyclic; digraph; feedback edge set; triangle free

Circular coloring triangle-free subcubic planar graphs ★★

Author(s): Ghebleh; Zhu

\begin{problem} Does every triangle-free planar graph of maximum degree three have circular chromatic number at most $\frac{20}{7}$? \end{problem}

Keywords: circular coloring; planar graph; triangle free

Unions of triangle free graphs ★★★

Author(s): Erdos; Hajnal

\begin{problem} Does there exist a graph with no subgraph isomorphic to $K_4$ which cannot be expressed as a union of $\aleph_0$ triangle free graphs? \end{problem}

Keywords: forbidden subgraph; infinite graph; triangle free

Triangle free strongly regular graphs ★★★


\begin{problem} Is there an eighth triangle free strongly regular graph? \end{problem}

Keywords: strongly regular; triangle free

Syndicate content