DIGRAPH GIRTH VIA CHROMATIC NUMBER

作者：Keevash Peter^*; Li Zhentao; Mohar Bojan; Reed Bruce

来源：SIAM Journal on Discrete Mathematics, 2013, 27(2): 693-696.

DOI：10.1137/120875892

• directed graphs
• graph coloring
• cycles

Let D be a digraph. The chromatic number chi(D) of D is the smallest number of colors needed to color the vertices of D such that every color class induces an acyclic subdigraph. The girth of D is the length of a shortest directed cycle, or infinity if D is acyclic. Let G(k, n) be the maximum possible girth of a digraph on n vertices with chi(D) %26gt; k. It is shown that G(k, n) %26gt;= left perpendicularn(1/k)right perpendicular and G(k, n) %26lt;= (3 log(2) n log(2) log(2) n)(1-1/k)n(1/k) for n %26gt;= 3 and k %26gt;= 2.

• 出版日期2013