Two results on the digraph chromatic number

DOI10.1016/J.DISC.2012.01.028zbMATH Open1242.05095arXiv1110.4898OpenAlexW2046546000MaRDI QIDQ418896FDOQ418896

Authors: Ararat Harutyunyan, Bojan Mohar 

Publication date: 30 May 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: It is known (Bollob'{a}s (1978); Kostochka and Mazurova (1977)) that there exist graphs of maximum degree $Delta$ and of arbitrarily large girth whose chromatic number is at least $cDelta/logDelta$. We show an analogous result for digraphs where the chromatic number of a digraph $D$ is defined as the minimum integer $k$ so that $V(D)$ can be partitioned into $k$ 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.

Full work available at URL: https://arxiv.org/abs/1110.4898

Recommendations

• Digraph girth via chromatic number
• A note on coloring digraphs of large girth
• Subdivisions of oriented cycles in digraphs with large chromatic number
• A short construction of highly chromatic digraphs without short cycles
• Strengthened Brooks' theorem for digraphs of girth at least three

zbMATH Keywords

chromatic numberdigraphdigraph coloringgirthdichromatic number

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• The circular chromatic number of a digraph
• Title not available (Why is that?)
• Strengthened Brooks' theorem for digraphs of girth at least three
• Eigenvalues and colorings of digraphs
• The dichromatic number of a digraph
• Packing directed circuits
• Chromatic number, girth and maximal degree
• Some extremal results in cochromatic and dichromatic theory
• Circular colorings of edge-weighted graphs
• Small odd cycles in 4-chromatic graphs
• Gallai's Theorem for List Coloring of Digraphs
• On the size of induced acyclic subgraphs in random digraphs
• On circuits and subgraphs of chromatic graphs
• Title not available (Why is that?)
• Short odd cycles in 4-chromatic graphs
• On coloring graphs with locally small chromatic number

Cited In (22)

• The \(m\)-degenerate chromatic number of a digraph
• Coloring digraphs with forbidden cycles
• Bounds for the dichromatic number of a generalized lexicographic product of digraphs
• New Bounds for the Dichromatic Number of a Digraph
• The geometry of noncommutative space-time
• Extension of Gyárfás-Sumner conjecture to digraphs
• Subdivisions in dicritical digraphs with large order or digirth
• Acyclic subgraphs of planar digraphs
• DICHROMATIC NUMBER AND FRACTIONAL CHROMATIC NUMBER
• Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of \(P_4\)
• Heroes in oriented complete multipartite graphs
• Heroes in Orientations of Chordal Graphs
• Generalized DP-colorings of graphs
• The star dichromatic number
• Four proofs of the directed Brooks' theorem
• On unavoidable digraphs in orientations of graphs
• Digraphs and Variable Degeneracy
• 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

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)