On the Harmonious Coloring of Graphs

DOI10.1137/0604032MaRDI QIDQ3331240zbMATH OpenOpenAlexWikidataFDO

Authors John Hopcroft, Mukkai S. Krishnamoorthy

Publication date 1983

Published in SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0604032

zbMATH Keywords

graceful numberharmonious coloringNP-complete

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Coloring of graphs and hypergraphs (05C15)

Recommendations

• The harmonious coloring problem is NP-complete for interval and permutation graphs
• The complexity of harmonious colouring for trees
• On the harmonious chromatic number of a graph
• Harmonious coloring on subclasses of colinear graphs
• The exact value of the harmonious chromatic number of a complete binary tree

Cites work

• scientific article; zbMATH DE number 3458691 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• On Additive Bases and Harmonious Graphs

Cited in

(47)

• Set colorings of graphs
• The harmonious coloring number of a graph
• The complexity of harmonious colouring for trees
• The exact value of the harmonious chromatic number of a complete binary tree
• On the harmonious chromatic number of a graph
• Harmonious chromatic number of directed graphs
• Coloring a dominating set without conflicts: \(q\)-subset square coloring
• The harmonious coloring problem is NP-complete for interval and permutation graphs
• Harmonious coloring: parameterized algorithms and upper bounds
• Harmonious colorings of digraphs.
• scientific article; zbMATH DE number 5914900 (Why is no real title available?)
• scientific article; zbMATH DE number 5856652 (Why is no real title available?)
• scientific article; zbMATH DE number 6099774 (Why is no real title available?)
• Harmonious coloring: parameterized algorithms and upper bounds
• scientific article; zbMATH DE number 5619926 (Why is no real title available?)
• Super total graceful graphs
• Harmonious coloring on subclasses of colinear graphs
• Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants
• Connection Matrices for MSOL-Definable Structural Invariants
• Graph labelings, embedding and NP-completeness theorems
• Harmonious coloring of trees with large maximum degree
• Strongly set-colorable graphs
• The Harmonious Chromatic Number of Almost All Trees
• On the harmonious coloring of collections of graphs
• The Harmonious Chromatic Number of Bounded Degree Trees
• Three algorithms for graph locally harmonious colouring
• Harmonic chromatic number of central graph of quadrilateral snakes
• Recursive axiomatisations from separation properties
• The edge-distinguishing chromatic number of petal graphs, chorded cycles, and spider graphs
• Harmonious colourings of graphs
• scientific article; zbMATH DE number 6288936 (Why is no real title available?)
• scientific article; zbMATH DE number 2230305 (Why is no real title available?)
• Harmonious and achromatic colorings of fragmentable hypergraphs
• Colouring a dominating set without conflicts: \(q\)-subset square colouring
• An \(iP_2\) extended star graph and its harmonious chromatic number
• On the harmonious chromatic number of graphs
• On the complexity of generalized chromatic polynomials
• The harmonious chromatic number of a complete binary and trinary tree
• The harmonious coloring game
• The asymptotic existence of BIBDs having a nesting
• A sharp upper bound for the harmonious total chromatic number of graphs and multigraphs
• Banff designs: difference methods for coloring incidence graphs
• Approximate and exact results for the harmonious chromatic number
• Harmonious colouring of line graph of commuting and non-commuting graph of \(D_{2n}\)
• The achromatic number and the pseudoachromatic number of caterpillars
• Parameterized Reunion with achromatic number
• NP-completeness results for some problems on subclasses of bipartite and chordal graphs

This page was built for publication: On the Harmonious Coloring of Graphs

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