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

4)\)-graphs4q\((q\(P_{4}\)-tidy graphsacyclic chromatic numbergreedy coloringsharmonious chromatic numberpolynomial time algorithmsqstar chromatic number

Mathematics Subject Classification ID

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

Recommendations

• Restricted coloring problems on graphs with few P₄'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

• 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₄'s
• Graph theory
• Grundy number on P₄-classes
• scientific article; zbMATH DE number 1375569 (Why is no real title available?)
• scientific article; zbMATH DE number 2147949 (Why is no real title available?)
• 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)

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