Restricted coloring problems on graphs with few

DOI10.1016/j.endm.2011.05.011zbMath1268.05194OpenAlexW72948258MaRDI QIDQ2840684

Cláudia Linhares Sales, K. Maia, Victor A. Campos, Nícolas A. Martins, Rudini Menezes Sampaio

Publication date: 23 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

acyclic chromatic numberstar chromatic numberharmonious chromatic numberpolynomial time algorithms\((qq\(P_{4}\)-tidy graphs4)\)-graphs4qgreedy colorings

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the structure of graphs with few \(P_4\)s
• Achromatic number is NP-complete for cographs and interval graphs
• Coloring with no 2-colored \(P_4\)'s
• The harmonious coloring problem is NP-complete for interval and permutation graphs
• Grundy number on -classes
• Star coloring of graphs
• On-line and first fit colorings of graphs
• Efficient algorithms for graphs with few \(P_4\)'s

This page was built for publication: Restricted coloring problems on graphs with few