Inapproximability of the lid-chromatic number

DOI10.1016/J.ENDM.2015.07.021zbMath1347.05074OpenAlexW2210463884MaRDI QIDQ324747

Nícolas A. Martins, Rudini Menezes Sampaio

Publication date: 17 October 2016

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

zbMATH Keywords

cographsinapproximability\(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)

Cites Work

• Unnamed Item
• Unnamed Item
• Locally identifying colourings for graphs with given maximum degree
• Locally identifying coloring of graphs
• Complement reducible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Locally identifying coloring in bounded expansion classes of graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• A Linear Recognition Algorithm for Cographs
• Vertex-distinguishing proper edge-colorings
• On a new class of codes for identifying vertices in graphs
• Vertex-distinguishing edge colorings of graphs

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