A construction of uniquely \(n\)-colorable digraphs with arbitrarily large digirth
type: Item
instance of: scholarly article
title: A construction of uniquely \(n\)-colorable digraphs with arbitrarily large digirth
zbMATH Open document ID: 1361.05060
author: Michael Severino
published in: The Electronic Journal of Combinatorics
publication date: 2017-05-18T00:00:00Z
full work available at URL: v24i2p1
review text: Summary: A natural digraph analogue of the graph-theoretic concept of an `independent set' is that of an `acyclic set', namely a set of vertices not spanning a directed cycle. Hence a digraph analogue of a graph coloring is a decomposition of the vertex set into acyclic sets and we say a digraph is uniquely \(n\)-colorable when this decomposition is unique up to relabeling. It was shown probabilistically in [\textit{A. Harutyunyan} et al., Can. J. Math. 64, No. 6, 1310--1328 (2012; Zbl 1254.05057)] that there exist uniquely \(n\)-colorable digraphs with arbitrarily large girth. Here we give a construction of such digraphs and prove that they have circular chromatic number \(n\). The graph-theoretic notion of `homomorphism' also gives rise to a digraph analogue. An acyclic homomorphism from a digraph \(D\) to a digraph \(H\) is a mapping \(\phi: V(D) \rightarrow V(H)\) such that \(uv \in A(D)\) implies that either \(\phi(u)\phi(v) \in A(H)\) or \(\phi(u)=\phi(v)\), and all the `fibers' \(\phi^{-1}(v)\), for \(v \in V(H)\), of \(\phi\) are acyclic. In this language, a core is a digraph \(D\) for which there does not exist an acyclic homomorphism from \(D\) to a proper subdigraph of itself. Here we prove some basic results about digraph cores and construct highly chromatic cores without short cycles.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 6719971
zbMATH Keywords: digraph
zbMATH Keywords: chromatic number
zbMATH Keywords: acyclic homomorphism
zbMATH Keywords: girth
MaRDI profile type: Publication
cites work: Q4500916
cites work: The circular chromatic number of a digraph
cites work: Q4050624
cites work: Q2716030
cites work: Uniquely D-colourable Digraphs with Large Girth
cites work: Strengthened Brooks' theorem for digraphs of girth at least three
cites work: A hypergraph-free construction of highly chromatic graphs without short cycles
cites work: On chromatic number of finite set-systems
cites work: Sur le coloriage des graphs
cites work: Q5672924
cites work: A short proof of the existence of highly chromatic hypergraphs without short cycles
cites work: The dichromatic number of a digraph
cites work: Q5499969
cites work: Q4256101
description: scientific article; zbMATH DE number 6719971