Inapproximability of the lid-chromatic number

DOI10.1016/J.ENDM.2015.07.021zbMATH Open1347.05074OpenAlexW2210463884MaRDI QIDQ324747FDOQ324747

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

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

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)

Cites Work

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

Cited In (4)

• Additive non-approximability of chromatic number in proper minor-closed classes
• Locally identifying coloring of graphs
• Relaxed locally identifying coloring of graphs
• 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)