Coloring dense digraphs
type: Item
instance of: scholarly article
title: Coloring dense digraphs
zbMATH Open document ID: 1449.05095
author: Ararat Harutyunyan
author: Tien-Nam Le
author: Alantha Newman
author: Stéphan Thomassé
published in: Combinatorica
publication date: 2020-01-17T00:00:00Z
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.
reviewed by: Peter Horák
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C42
zbMATH DE Number: 7153032
zbMATH Keywords: coloring
zbMATH Keywords: digraph
zbMATH Keywords: hero
zbMATH Keywords: superhero
MaRDI profile type: MaRDI publication profile
full work available at URL: s00493-019-3815-8
OpenAlex ID: W2978551732
Wikidata QID: Q126984469
DOI: 10.1007/S00493-019-3815-8
Recommended article: Coloring dense digraphs
Recommended article: Coloring Graphs with Dense Neighborhoods
Recommended article: Coloring and Covering Nowhere Dense Graphs
Recommended article: The complexity of colouring problems on dense graphs
Recommended article: Colouring and Covering Nowhere Dense Graphs
Recommended article: On DP‐coloring of digraphs
Recommended article: Coloring digraphs with forbidden cycles
Recommended article: Set colorings of digraphs
Recommended article: Colorings in digraphs from the spectral radius
Recommended article: \(H\)-colorings of dense hypergraphs
description: scientific article; zbMATH DE number 7153032