Restricted coloring problems on graphs with few P₄'s

DOI10.1007/S10479-014-1537-2MaRDI QIDQ490171zbMATH OpenOpenAlexFDO

Authors Ana Karolinna Maia, Cláudia L. Sales, N. Martins, Rudini M. Sampaio

Publication date 22 January 2015

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10479-014-1537-2

zbMATH Keywords

acyclic coloringcographsstar coloringfixed parameter algorithms\((q,q-4)\)-graphsclique coloringharmonic coloringnonrepetitive coloringprimeval decompositionThue chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• Restricted coloring problems on graphs with few \(P'_4s\)
• Acyclic and star coloring of \(P_4\)-reducible and \(P_4\)-sparse graphs
• Maximization coloring problems on graphs with few \(P_4\)
• Efficient algorithms for graphs with few \(P_4\)'s
• scientific article; zbMATH DE number 1375569

Cites work

• scientific article; zbMATH DE number 1375569 (Why is no real title available?)
• scientific article; zbMATH DE number 3595210 (Why is no real title available?)
• scientific article; zbMATH DE number 2104720 (Why is no real title available?)
• A New Class of Brittle Graphs
• Achromatic number is NP-complete for cographs and interval graphs
• Acyclic and star colorings of cographs
• Automorphism groups of graphs with 1-factorizations
• Coloring the Maximal Cliques of Graphs
• Efficient algorithms for graphs with few \(P_4\)'s
• Exploring the complexity boundary between coloring and list-coloring
• Graph theory
• Nonrepetitive colorings of graphs
• Nonrepetitive colorings of graphs -- a survey
• Nonrepetitive list colourings of paths
• Notes on nonrepetitive graph colouring
• On acyclic colorings of planar graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• On the structure of graphs with few \(P_4\)s
• P-Components and the Homogeneous Decomposition of Graphs
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Star coloring of graphs
• The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
• The complexity of nonrepetitive coloring
• The harmonious coloring problem is NP-complete for interval and permutation graphs
• Thue type problems for graphs, points, and numbers
• Two fixed-parameter algorithms for the cocoloring problem
• \(P_{4}\)-laden graphs: A new class of brittle graphs

Cited in

(12)

• Spy game: FPT-algorithm and results on graph products
• Graphs with few \(P_4\)'s under the convexity of paths of order three
• Restricted coloring problems on graphs with few \(P'_4s\)
• PSPACE-completeness of two graph coloring games
• Acyclic, star, and injective colouring: bounding the diameter
• Hardness transitions and uniqueness of acyclic colouring
• On the minimum sum coloring of \(P_4\)-sparse graphs
• Acyclic and star coloring of \(P_4\)-reducible and \(P_4\)-sparse graphs
• Spy game: FPT-algorithm, hardness and graph products
• Acyclic and star colorings of cographs
• scientific article; zbMATH DE number 7651161 (Why is no real title available?)
• Maximization coloring problems on graphs with few \(P_4\)

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

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