Abstract: It is known (Bollob'{a}s (1978); Kostochka and Mazurova (1977)) that there exist graphs of maximum degree and of arbitrarily large girth whose chromatic number is at least . We show an analogous result for digraphs where the chromatic number of a digraph is defined as the minimum integer so that can be partitioned into acyclic sets, and the girth is the length of the shortest cycle in the corresponding undirected graph. It is also shown, in the same vein as an old result of Erdos (1962), that there are digraphs with arbitrarily large chromatic number where every large subset of vertices is 2-colorable.
Recommendations
Cites work
- scientific article; zbMATH DE number 3659621 (Why is no real title available?)
- scientific article; zbMATH DE number 53883 (Why is no real title available?)
- scientific article; zbMATH DE number 1498519 (Why is no real title available?)
- Chromatic number, girth and maximal degree
- Circular colorings of edge-weighted graphs
- Eigenvalues and colorings of digraphs
- Gallai's theorem for list coloring of digraphs
- On circuits and subgraphs of chromatic graphs
- On coloring graphs with locally small chromatic number
- On the size of induced acyclic subgraphs in random digraphs
- Packing directed circuits
- Short odd cycles in 4-chromatic graphs
- Small odd cycles in 4-chromatic graphs
- Some extremal results in cochromatic and dichromatic theory
- Strengthened Brooks' theorem for digraphs of girth at least three
- The circular chromatic number of a digraph
- The dichromatic number of a digraph
Cited in
(33)- The \(m\)-degenerate chromatic number of a digraph
- Heroes in orientations of chordal graphs
- Coloring digraphs with forbidden cycles
- Subdivisions of oriented cycles in digraphs with large chromatic number
- Strengthened Brooks' theorem for digraphs of girth at least three
- Bounds for the dichromatic number of a generalized lexicographic product of digraphs
- A note on coloring digraphs of large girth
- Digraphs and variable degeneracy
- The geometry of noncommutative space-time
- Extension of Gyárfás-Sumner conjecture to digraphs
- New Bounds for the Dichromatic Number of a Digraph
- A short construction of highly chromatic digraphs without short cycles
- Planar digraphs without large acyclic sets
- Dichromatic number and fractional chromatic number
- Uniquely \(D\)-colourable digraphs with large girth. II: Simplification via generalization
- Generalized signed graphs of large girth and large chromatic number
- Subdivisions in dicritical digraphs with large order or digirth
- Acyclic subgraphs of planar digraphs
- Coloring dense digraphs
- Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of \(P_4\)
- Heroes in oriented complete multipartite graphs
- Digraph girth via chromatic number
- The star dichromatic number
- Generalized DP-colorings of graphs
- Four proofs of the directed Brooks' theorem
- On unavoidable digraphs in orientations of graphs
- Coloring tournaments: from local to global
- \((\overrightarrow{P_6}\), triangle)-free digraphs have bounded dichromatic number
- Paths with two blocks in k-chromatic digraphs
- The edge density of critical digraphs
- Coloring \(k\)-partite sparse digraphs
- Chordal directed graphs are not \(\chi\)-bounded
- A construction of uniquely \(n\)-colorable digraphs with arbitrarily large digirth
This page was built for publication: Two results on the digraph chromatic number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q418896)
