Concerning the achromatic number of graphs

DOI10.1016/0095-8956(86)90062-6zbMath0577.05032OpenAlexW1969921821WikidataQ55966839 ScholiaQ55966839MaRDI QIDQ1065819

Geňa Hahn, Martin Farber, Pavol Hell, Donald J. Miller

Publication date: 1986

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(86)90062-6

zbMATH Keywords

computational complexityupper boundsNP-completenessbipartite graphstreespolynomial algorithmsachromatic number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (16)

Minimal graphs that fold onto \(K_ n\) ⋮ Reduction graph and its application on algebraic graphs ⋮ Achromatic number of collections of paths and cycles ⋮ Generalising the achromatic number to Zaslavsky's colourings of signed graphs ⋮ Complete acyclic colorings ⋮ Complete oriented colourings and the oriented achromatic number ⋮ Bounding the pseudoachromatic index of the complete graph via projective planes ⋮ On the achromatic number of signed graphs ⋮ Þ-energy of generalized Petersen graphs ⋮ Graph colourings and partitions ⋮ Achromatic number of fragmentable graphs ⋮ Efficient approximation algorithms for the achromatic number ⋮ Complete colourings of hypergraphs ⋮ NP-completeness results for some problems on subclasses of bipartite and chordal graphs ⋮ On the pseudoachromatic index of the complete graph ⋮ The b-chromatic number of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower estimate for the achromatic number of irreducible graphs
• Graph with given achromatic number
• Eigenvalues and partitionings of the edges of a graph
• Edge Dominating Sets in Graphs
• Homomorphism Interpolation and Approximation
• On the complexity of the general coloring problem
• Subtree Isomorphism in O(n5/2)
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

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