2019/06/28 by Pavol Hell, Feder, Tom\' as, Hell, Pavol +3 · 1 citation
Computer Science · Mathematics · #05C15 #05C20 #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1907.00061
openalex publication_date 2019/06/28 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
We consider acyclic r-colorings in graphs and digraphs: they color the\nvertices in r colors, each of which induces an acyclic graph or digraph. (This\nincludes the dichromatic number of a digraph, and the arboricity of a graph.)\nFor any girth and sufficiently high degree, we prove the NP-completeness of\nacyclic r-colorings; our method also implies the known analogue for classical\ncolorings. The proofs use high girth graphs with high arboricity and\ndichromatic numbers. High girth graphs and digraphs with high chromatic and\ndichromatic numbers have been well studied; we re-derive the results from a\ngeneral result about relational systems, which also implies the similar fact\nabout high girth and high arboricity used in the proofs. These facts concern\ngraphs and digraphs of high girth and low degree; we contrast them by\nconsidering acyclic colorings of tournaments (which have low girth and high\ndegree). We prove that even though acyclic two-colorability of tournaments is\nknown to be NP-complete, random acyclically r-colorable tournaments allow\nrecovering an acyclic r-coloring in deterministic linear time, with high\nprobablity.\n