Injective coloring of some subclasses of bipartite graphs and chordal graphs

DOI10.1016/J.DAM.2020.12.006MaRDI QIDQ2659063zbMATH OpenOpenAlexFDO

Authors 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 algorithminapproximabilityinjective coloringNP-completenesspolynomial time algorithm

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of injective colorings and its generalizations
• On Injective Colourings of Chordal Graphs
• Complexity and algorithms for injective edge-coloring in graphs
• Injective colorings with arithmetic constraints
• On the injective chromatic number of graphs

Cites work

• A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
• A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
• A linear time recognition algorithm for proper interval graphs
• A review of tree convex sets test
• Classes of bipartite graphs related to chordal graphs
• Domination in some subclasses of bipartite graphs
• Hamiltonicity in Split Graphs - A Dichotomy
• scientific article; zbMATH DE number 4152428 (Why is no real title available?)
• Injective coloring of planar graphs
• Injective coloring of plane graphs with girth 5
• Injective coloring of some graph operations
• Injective colorings of graphs with low average degree
• Injective colorings of planar graphs with few colors
• Injective colorings of sparse graphs
• On Injective Colourings of Chordal Graphs
• On the complexity of injective colorings and its generalizations
• On the injective chromatic number of graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The fractional chromatic number of mycielski's graphs
• Threshold graphs and related topics
• Zero knowledge and the chromatic number

Cited in

(14)

• Complexity and algorithms for neighbor-sum-2-distinguishing \(\{1,3\}\)-edge-weighting of graphs
• Exact square coloring of certain classes of graphs: complexity and algorithms
• Injective coloring of graphs revisited
• Injective L(2,1)-coloring as an optimization problem on the set of permutations of graph vertices: domishold graphs
• On the complexity of injective colorings and its generalizations
• On Injective Colourings of Chordal Graphs
• Exact square coloring of graphs resulting from some graph operations and products
• Complexity and algorithms for injective edge coloring of graphs
• Packings in bipartite prisms and hypercubes
• Injective edge coloring of some standard graph products
• Injective coloring of subclasses of chordal graphs
• Injective coloring of generalized Mycielskian of graphs
• Injective colorings of Sierpiński-like graphs and Kneser graphs
• e-injective coloring: 2-distance and injective coloring conjectures

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

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