On Injective Colourings of Chordal Graphs

DOI10.1007/978-3-540-78773-0_45zbMath1136.68463OpenAlexW1929096065MaRDI QIDQ5458556

Juraj Stacho, Andre Raspaud, Pavol Hell

Publication date: 15 April 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78773-0_45

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (18)

On injective chromatic polynomials of graphs ⋮ Injective coloring of some graph operations ⋮ Injective coloring of some subclasses of bipartite graphs and chordal graphs ⋮ Connectivity of minimum non-5-injectively colorable planar cubic graphs ⋮ Partitions of graphs into cographs ⋮ On the complexity of injective colorings and its generalizations ⋮ Injective colorings with arithmetic constraints ⋮ Complexity and algorithms for injective edge coloring of graphs ⋮ Unnamed Item ⋮ Polarity of chordal graphs ⋮ On the algorithmic aspects of strong subcoloring ⋮ The complexity of frugal colouring ⋮ Join colourings of chordal graphs ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Solving partition problems with colour-bipartitions ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ Injective colouring for H-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• List matrix partitions of chordal graphs
• Polarity of chordal graphs
• Characterizations of strongly chordal graphs
• On powers and centers of chordal graphs
• Decomposition by clique separators
• Zero knowledge and the chromatic number
• Partitioning chordal graphs into independent sets and cliques
• On the injective chromatic number of graphs
• Labelling Graphs with a Condition at Distance 2
• Approximations for  -Colorings of Graphs
• Partial covers of graphs
• Coloring Powers of Chordal Graphs

This page was built for publication: On Injective Colourings of Chordal Graphs