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)

Full work available at URL https://doi.org/10.1016/0166-218X(94)00100-R

zbMATH Keywords

complexityharmonious colouringnumber of colourstree

Mathematics Subject Classification ID

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

Review text

A harmonious colouring of a simple graph is a proper vertex colouring such that each pair of colours appear together on at most one edge. It is shown in the paper that the problem of determining the least number of colours in a harmonious colouring of a tree is NP-hard.

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

(36)

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

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)