Injective colorings with arithmetic constraints

DOI10.1007/s00373-014-1520-3zbMath1327.05098OpenAlexW2060730025WikidataQ114229667 ScholiaQ114229667MaRDI QIDQ897262

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

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)

Cites Work

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

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