Injective colorings with arithmetic constraints

DOI10.1007/S00373-014-1520-3MaRDI QIDQ897262zbMATH OpenOpenAlexWikidataFDO

Authors Natacha Astromujoff, Mathieu Chapelle, Martin Matamala, Ioan Todinca, José Zamora

Publication date 17 December 2015

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10533/147976

zbMATH Keywords

dynamic programmingNP-completenesspolynomial time algorithmsinjective colorings

Mathematics Subject Classification ID

Dynamic programming (90C39) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Injective coloring of graphs revisited
• On the complexity of injective colorings and its generalizations
• Almost injective colorings
• Injective oriented colourings
• Counterexamples to a conjecture on injective colorings
• scientific article; zbMATH DE number 7404447
• Injective colorings of planar graphs with few colors
• Injective coloring of planar graphs
• Injective coloring of planar graphs
• Injective colorings of sparse graphs

Cites work

• scientific article; zbMATH DE number 3071148 (Why is no real title available?)
• A Linear Time Algorithm for L(2,1)-Labeling of Trees
• Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
• Finding large 3-free sets. I. The small \(n\) case
• Integer Sets Containing No Arithmetic Progressions
• Integer sets containing no arithmetic progressions
• Labelling Graphs with a Condition at Distance 2
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On Certain Sets of Integers
• On Injective Colourings of Chordal Graphs
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• On the injective chromatic number of graphs
• On triples in arithmetic progression
• The $L(2,1)$-Labeling Problem on Graphs
• The NP-Completeness of Edge-Coloring
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Zero knowledge and the chromatic number

Cited in

(7)

• Almost injective colorings
• On the additive chromatic number of several families of graphs
• On Injective Colourings of Chordal Graphs
• On the complexity of injective colorings and its generalizations
• The inapproximability for the \((0,1)\)-additive number
• scientific article; zbMATH DE number 2237565 (Why is no real title available?)
• Injective coloring of some subclasses of bipartite graphs and chordal graphs

This page was built for publication: Injective colorings with arithmetic constraints

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