The complexity of harmonious colouring for trees

DOI10.1016/0166-218X(94)00100-RMaRDI QIDQ1346692zbMATH OpenWikidataFDO

Authors Keith Edwards, Colin McDiarmid

Publication date 10 April 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

treecomplexityharmonious colouringnumber of colours

Mathematics Subject Classification ID

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

Recommendations

• The exact value of the harmonious chromatic number of a complete binary tree
• Harmonious coloring on subclasses of colinear graphs
• On the Harmonious Coloring of Graphs
• On harmonious colouring of trees
• On the harmonious colouring of trees.

Cites work

• scientific article; zbMATH DE number 4134074 (Why is no real title available?)
• scientific article; zbMATH DE number 3795986 (Why is no real title available?)
• New upper bounds on harmonious colorings
• On the Harmonious Coloring of Graphs

Cited in

(30)

• NP-completeness results for some problems on subclasses of bipartite and chordal graphs
• Homomorphisms of 2-edge-colored graphs
• On the Grundy number of Cameron graphs
• On the complexity of role colouring planar graphs, trees and cographs
• The harmonious chromatic number of complete \(r\)-ary trees
• The Harmonious Chromatic Number of Bounded Degree Trees
• Harmonious coloring on subclasses of colinear graphs
• The achromatic number of bounded degree trees
• Complete partitions of graphs
• Harmonious coloring of trees with large maximum degree
• On the Harmonious Coloring of Graphs
• Counting Unlabelled Subtrees of a Tree is #P-complete
• The harmonious coloring problem is NP-complete for interval and permutation graphs
• Colored homomorphisms of colored mixed graphs
• Geometric achromatic and pseudoachromatic indices
• Harmonious coloring: parameterized algorithms and upper bounds
• On the pseudo-achromatic number problem
• VLSI layout of Benes networks
• Evaluations of Graph Polynomials
• Complete colourings of hypergraphs
• Harmonious coloring: parameterized algorithms and upper bounds
• Minimum order of graphs with given coloring parameters
• Homomorphisms of 2-edge-colored graphs
• On the Pseudo-achromatic Number Problem
• Some notes on bounded starwidth graphs
• The Harmonious Chromatic Number of Almost All Trees
• Harmonious colourings of graphs
• Connection Matrices for MSOL-Definable Structural Invariants
• Three algorithms for graph locally harmonious colouring
• On the complexity of generalized chromatic polynomials

This page was built for publication: The complexity of harmonious colouring for trees

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