On the complexity of injective colorings and its generalizations

DOI10.1016/j.tcs.2013.04.026zbMath1277.68089WikidataQ114129181 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

complexity; algorithm; injective coloring; max-injective coloring; on-line injective coloring

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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

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