Injective coloring of some subclasses of bipartite graphs and chordal graphs

DOI10.1016/j.dam.2020.12.006zbMath1460.05066OpenAlexW3113273579MaRDI QIDQ2659063

B. S. Panda, Priyamvada

Publication date: 25 March 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.12.006

zbMATH Keywords

graph algorithmpolynomial time algorithmNP-completenessinapproximabilityinjective coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

Exact square coloring of certain classes of graphs: complexity and algorithms ⋮ Exact square coloring of graphs resulting from some graph operations and products ⋮ Complexity and algorithms for injective edge coloring of graphs ⋮ Injective coloring of graphs revisited ⋮ Packings in bipartite prisms and hypercubes ⋮ Complexity and algorithms for neighbor-sum-2-distinguishing \(\{1,3\}\)-edge-weighting of graphs

Cites Work

• Unnamed Item
• On the complexity of injective colorings and its generalizations
• Injective coloring of plane graphs with girth 5
• Injective colorings of graphs with low average degree
• Injective colorings of sparse graphs
• A linear time recognition algorithm for proper interval graphs
• Injective colorings of planar graphs with few colors
• Classes of bipartite graphs related to chordal graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Zero knowledge and the chromatic number
• Domination in some subclasses of bipartite graphs
• Injective coloring of some graph operations
• On the injective chromatic number of graphs
• Threshold graphs and related topics
• A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
• Hamiltonicity in Split Graphs - A Dichotomy
• A REVIEW OF TREE CONVEX SETS TEST
• The fractional chromatic number of mycielski's graphs
• A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
• On Injective Colourings of Chordal Graphs
• Injective coloring of planar graphs

This page was built for publication: Injective coloring of some subclasses of bipartite graphs and chordal graphs