Inapproximability of the lid-chromatic number

DOI10.1016/J.ENDM.2015.07.021MaRDI QIDQ324747zbMATH OpenOpenAlexFDO

Authors N. Martins, Rudini M. Sampaio

Publication date 17 October 2016

Full work available at URL https://doi.org/10.1016/j.endm.2015.07.021

zbMATH Keywords

inapproximabilitycographs\(P_4\)-sparse graphslocally identifying coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Recommendations

• Locally identifying coloring of graphs with few P4s
• Locally identifying coloring of graphs
• Locally identifying coloring in bounded expansion classes of graphs
• Relaxed locally identifying coloring of graphs
• Locally identifying colourings for graphs with given maximum degree

Cites work

• scientific article; zbMATH DE number 3896983 (Why is no real title available?)
• scientific article; zbMATH DE number 907924 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A tree representation for \(P_ 4\)-sparse graphs
• Complement reducible graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Locally identifying coloring in bounded expansion classes of graphs
• Locally identifying coloring of graphs
• Locally identifying colourings for graphs with given maximum degree
• On a new class of codes for identifying vertices in graphs
• Vertex-distinguishing edge colorings of graphs
• Vertex-distinguishing proper edge-colorings

Cited in

(5)

• Relaxed locally identifying coloring of graphs
• Locally identifying coloring in some chordal graphs
• Locally identifying coloring of graphs
• Additive non-approximability of chromatic number in proper minor-closed classes
• Locally identifying coloring in bounded expansion classes of graphs

This page was built for publication: Inapproximability of the lid-chromatic number

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