Systems of pairs of \(q\)-distant representatives, and graph colorings

DOI10.1007/s10958-005-0059-5zbMath1078.05031OpenAlexW1995073880MaRDI QIDQ2577585

Petr A. Golovach

Publication date: 3 January 2006

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10958-005-0059-5

zbMATH Keywords

NP-completeness

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Distance Constrained Labelings of Trees ⋮ Distance three labelings of trees ⋮ Parameterized complexity of coloring problems: treewidth versus vertex cover ⋮ Systems of distant representatives

Cites Work

• Labelling Graphs with a Condition at Distance 2
• The $L(2,1)$-Labeling Problem on Graphs
• Fixed-parameter complexity of \(\lambda\)-labelings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Systems of pairs of \(q\)-distant representatives, and graph colorings