Restricted coloring problems on graphs with few P'_4s

DOI10.1016/J.ENDM.2011.05.011MaRDI QIDQ2840684zbMATH OpenOpenAlexFDO

Authors Victor Campos, Cláudia L. Sales, K. Maia, N. Martins, Rudini M. 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 numberpolynomial time algorithms\((qstar chromatic numberharmonious chromatic numberq\(P_{4}\)-tidy graphs4)\)-graphs4qgreedy colorings

Mathematics Subject Classification ID

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

Recommendations

• Restricted coloring problems on graphs with few \(P_4\)'s
• Maximization coloring problems on graphs with few \(P_4\)
• On the Grundy number of graphs with few P₄'s
• Four-coloring \(P_6\)-free graphs
• Acyclic and star coloring of \(P_4\)-reducible and \(P_4\)-sparse graphs

Cites work

• scientific article; zbMATH DE number 1375569 (Why is no real title available?)
• scientific article; zbMATH DE number 2147949 (Why is no real title available?)
• Achromatic number is NP-complete for cographs and interval graphs
• Coloring with no 2-colored \(P_4\)'s
• Efficient algorithms for graphs with few \(P_4\)'s
• Graph theory
• Grundy number on \(P_4\)-classes
• On the structure of graphs with few P₄s
• On-line and first fit colorings of graphs
• Star coloring of graphs
• The harmonious coloring problem is NP-complete for interval and permutation graphs

Cited in

(8)

• Two fixed-parameter algorithms for the cocoloring problem
• Maximization coloring problems on graphs with few \(P_4\)
• Recognition algorithm for \(P_4\)-tidy graphs
• Grundy number on \(P_4\)-classes
• On the minimum sum coloring of P₄-sparse graphs
• Restricted coloring problems on graphs with few \(P_4\)'s
• Efficient algorithms for graphs with few \(P_4\)'s
• Acyclic and star coloring of \(P_4\)-reducible and \(P_4\)-sparse graphs

This page was built for publication: Restricted coloring problems on graphs with few \(P'_4s\)

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