Coloring dense digraphs

DOI10.1007/S00493-019-3815-8MaRDI QIDQ5919339zbMATH OpenOpenAlexWikidataFDO

Authors Ararat Harutyunyan, Tien-Nam Le, Alantha Newman, Stéphan Thomassé

Publication date 17 January 2020

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-019-3815-8

zbMATH Keywords

coloringdigraphherosuperhero

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Density (toughness, etc.) (05C42)

Review text

Let \(\alpha (D),\chi (D)\) denote the independence and the chromatic number of a digraph \(D,\) respectively. A tournament \ \(S\) is called a hero, if there is a number \(f(S)\) such that \(\chi (T)\leq f(S)\) for every tournament \(T\) that does not contain \(S\) as an induced subgraph. \textit{E. Berger} et al. [J. Comb. Theory, Ser. B 103, No. 1, 1--20 (2013; Zbl 1254.05064)] fully characterized the class of heroes. In this paper, the authors introduce a notion of a superhero. A digraph \(H\) is called a superhero if for every \(\alpha \geq 1,\) there is a number \(g(H,\alpha )\) such that \(\chi (D)\leq g(H,\alpha )\) for every digraph \(D\), \(\alpha (D)=\alpha ,\) that does not contain \(H\) as an induced subgraph. The main result of the paper states that a digraph is a superhero if and only if it is a hero.

Recommendations

• Coloring dense digraphs
• Coloring Graphs with Dense Neighborhoods
• Coloring and covering nowhere dense graphs
• The complexity of colouring problems on dense graphs
• Colouring and covering nowhere dense graphs
• On DP‐coloring of digraphs
• Coloring digraphs with forbidden cycles
• Set colorings of digraphs
• Colorings in digraphs from the spectral radius
• \(H\)-colorings of dense hypergraphs

Cited in

(14)

• Tournaments and colouring
• Extension of Gyárfás-Sumner conjecture to digraphs
• Set colorings of digraphs
• Heroes in orientations of chordal graphs
• Strong complete minors in digraphs
• Coloring dense digraphs
• Complete directed minors and chromatic number
• Four proofs of the directed Brooks' theorem
• Heroes in oriented complete multipartite graphs
• Coloring tournaments with few colors: algorithms and complexity
• On heroes in digraphs with forbidden induced forests
• \((\overrightarrow{P_6}\), triangle)-free digraphs have bounded dichromatic number
• The dichromatic number of digraphs without induced subdigraphs
• Clique number of tournaments

This page was built for publication: Coloring dense digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5919339)