Triangle-free graphs of tree-width t are ⌈ (t+3)/2 ⌉-colorable.
Zdenek DvorákKen-ichi KawarabayashiPublished in: Eur. J. Comb. (2017)
Keyphrases
- tree width
- tree decomposition
- structural properties
- series parallel
- graph theory
- relational structures
- constraint networks
- shortest path
- graph matching
- computationally challenging
- complex networks
- lower bound
- conjunctive queries
- parallel processing
- database
- probabilistic reasoning
- decomposition method
- exact and approximate
- expert systems
- databases