Restricted coloring problems on graphs with few \(P_4\)'s

DOI10.1007/s10479-014-1537-2zbMath1306.05068OpenAlexW2015151531MaRDI QIDQ490171

Ana Karolinna Maia, Cláudia Linhares Sales, Rudini Menezes Sampaio, Nícolas A. Martins

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

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (7)

PSPACE-completeness of two graph coloring games ⋮ Spy game: FPT-algorithm, hardness and graph products ⋮ Hardness transitions and uniqueness of acyclic colouring ⋮ Unnamed Item ⋮ Spy game: FPT-algorithm and results on graph products ⋮ Graphs with few \(P_4\)'s under the convexity of paths of order three ⋮ Acyclic, star, and injective colouring: bounding the diameter

Cites Work

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

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