On the complexity of injective colorings and its generalizations

DOI10.1016/j.tcs.2013.04.026zbMath1277.68089OpenAlexW2065347418WikidataQ114129181 ScholiaQ114129181MaRDI QIDQ387816

Jing Jin, Xiaoyan Zhang, Bao-Gang Xu

Publication date: 17 December 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.04.026

zbMATH Keywords

complexityalgorithminjective coloringmax-injective coloringon-line injective coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Injective coloring of some subclasses of bipartite graphs and chordal graphs ⋮ Connectivity of minimum non-5-injectively colorable planar cubic graphs ⋮ Complexity and algorithms for injective edge coloring of graphs ⋮ Unnamed Item ⋮ Injective coloring of graphs revisited ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Injective colouring for H-free graphs

Cites Work

• Unnamed Item
• A coloring problem for weighted graphs
• The 2nd-order conditional 3-coloring of claw-free graphs
• An on-line graph coloring algorithm with sublinear performance ratio
• Zero knowledge and the chromatic number
• Coloring inductive graphs on-line
• On the injective chromatic number of graphs
• A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
• Max-coloring and online coloring with bandwidths on interval graphs
• A New Algorithm for On-line Coloring Bipartite Graphs
• On-line and first fit colorings of graphs
• The fractional chromatic number of mycielski's graphs
• On Injective Colourings of Chordal Graphs

This page was built for publication: On the complexity of injective colorings and its generalizations