Complete acyclic colorings

DOI10.37236/8752zbMATH Open1441.05073arXiv1905.08670OpenAlexW3030182375MaRDI QIDQ2185231FDOQ2185231

Authors: Winfried. Hochstättler, Kolja Knauer, Raphael Steiner, Stefan Felsner 

Publication date: 4 June 2020

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We study two parameters that arise from the dichromatic number and the vertex-arboricity in the same way that the achromatic number comes from the chromatic number. The adichromatic number of a digraph is the largest number of colors its vertices can be colored with such that every color induces an acyclic subdigraph but merging any two colors yields a monochromatic directed cycle. Similarly, the a-vertex arboricity of an undirected graph is the largest number of colors that can be used such that every color induces a forest but merging any two yields a monochromatic cycle. We study the relation between these parameters and their behavior with respect to other classical parameters such as degeneracy and most importantly feedback vertex sets.

Full work available at URL: https://arxiv.org/abs/1905.08670

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• The diachromatic number of digraphs
• Publication:3480066
• Acyclic and oriented chromatic numbers of graphs
• Complete oriented colourings and the oriented achromatic number
• scientific article; zbMATH DE number 4053646

zbMATH Keywords

adichromatic number of a digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• The Point-Arboricity of Planar Graphs
• The point-arboricity of a graph
• On Independent Circuits Contained in a Graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• The chromatic number of random graphs
• Packing directed circuits
• Concerning the achromatic number of graphs
• Title not available (Why is that?)
• The diachromatic number of digraphs
• Harmonious chromatic number of directed graphs
• Planar Digraphs of Digirth Four are 2-Colorable
• Coloring tournaments: from local to global
• DICHROMATIC NUMBER AND FRACTIONAL CHROMATIC NUMBER

Cited In (5)

• Vertex coloring acyclic digraphs and their corresponding hypergraphs
• On sensitivity in bipartite Cayley graphs
• Title not available (Why is that?)
• Extendiendo un resultado de coloraciones de gráficas a coloraciones de digráficas
• Achromatic arboricity on complete graphs

This page was built for publication: Complete acyclic colorings

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