Complete acyclic colorings

DOI10.37236/8752zbMATH Open1441.05073OpenAlexW3030182375MaRDI 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

• scientific article; zbMATH DE number 994578 (Why is no real title available?)
• scientific article; zbMATH DE number 1057876 (Why is no real title available?)
• scientific article; zbMATH DE number 3298599 (Why is no real title available?)
• Coloring tournaments: from local to global
• Concerning the achromatic number of graphs
• Dichromatic number and fractional chromatic number
• Harmonious chromatic number of directed graphs
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• On Independent Circuits Contained in a Graph
• Packing directed circuits
• Planar digraphs of digirth four are 2-colorable
• The Point-Arboricity of Planar Graphs
• The chromatic number of random graphs
• The diachromatic number of digraphs
• The point-arboricity of a graph

Cited In (6)

• Vertex coloring acyclic digraphs and their corresponding hypergraphs
• On sensitivity in bipartite Cayley graphs
• Title not available (Why is no real title available?)
• The diachromatic number of digraphs
• 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)