Complete acyclic colorings

DOI10.37236/8752MaRDI QIDQ2185231zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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

zbMATH Keywords

adichromatic number of a digraph

Mathematics Subject Classification ID

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

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.

Recommendations

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

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
• scientific article; zbMATH DE number 4150191 (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)