On the achromatic number of signed graphs

DOI10.1016/j.tcs.2019.01.006zbMath1405.05063arXiv1902.04828OpenAlexW2963121347WikidataQ128632363 ScholiaQ128632363MaRDI QIDQ1711838

Dimitri Lajou

Publication date: 18 January 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

achromatic numbersigned graphNP-complete problemtwo-edge colored graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Signed and weighted graphs (05C22)

Related Items (2)

Generalising the achromatic number to Zaslavsky's colourings of signed graphs ⋮ Concepts of signed graph coloring

Cites Work

• Unnamed Item
• Unnamed Item
• Complete oriented colourings and the oriented achromatic number
• Concerning the achromatic number of graphs
• A lower estimate for the achromatic number of irreducible graphs
• Signed graphs
• Graph with given achromatic number
• Homomorphisms of edge-colored graphs and Coxeter groups
• The diachromatic number of digraphs
• Achromatic number is NP-complete for cographs and interval graphs
• The dichromatic number of a digraph
• Harmonious chromatic number of directed graphs
• Eigenvalues and partitionings of the edges of a graph
• On the notion of balance of a signed graph
• Edge Dominating Sets in Graphs
• Homomorphisms of Signed Graphs
• The achromatic number of a graph

This page was built for publication: On the achromatic number of signed graphs