Restricted coloring problems on graphs with few \(P_4\)'s
From MaRDI portal
Publication:490171
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
cographsacyclic coloringstar coloringfixed parameter algorithms\((q,q-4)\)-graphsclique coloringharmonic coloringnonrepetitive coloringprimeval decompositionThue chromatic number
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
