Restricted coloring problems on graphs with few P₄'s
DOI10.1007/S10479-014-1537-2zbMATH Open1306.05068OpenAlexW2015151531MaRDI QIDQ490171FDOQ490171
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
Recommendations
acyclic coloringcographsstar coloringfixed parameter algorithms\((q,q-4)\)-graphsclique coloringharmonic coloringnonrepetitive coloringprimeval decompositionThue chromatic number
Cites Work
- Graph theory
- On acyclic colorings of planar graphs
- Star coloring of graphs
- Acyclic and star colorings of cographs
- A New Class of Brittle Graphs
- Title not available (Why is that?)
- Nonrepetitive list colourings of paths
- Nonrepetitive colorings of graphs
- Nonrepetitive colorings of graphs -- a survey
- Thue type problems for graphs, points, and numbers
- The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
- On the structure of graphs with few \(P_4\)s
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Achromatic number is NP-complete for cographs and interval graphs
- Exploring the complexity boundary between coloring and list-coloring
- The complexity of nonrepetitive coloring
- Coloring the Maximal Cliques of Graphs
- \(P_{4}\)-laden graphs: A new class of brittle graphs
- P-Components and the Homogeneous Decomposition of Graphs
- Notes on nonrepetitive graph colouring
- Automorphism groups of graphs with 1-factorizations
- The harmonious coloring problem is NP-complete for interval and permutation graphs
- Two fixed-parameter algorithms for the cocoloring problem
- Title not available (Why is that?)
- On the complexity of bicoloring clique hypergraphs of graphs
- Title not available (Why is that?)
- Efficient algorithms for graphs with few \(P_4\)'s
Cited In (9)
- Hardness transitions and uniqueness of acyclic colouring
- Acyclic and star colorings of cographs
- Acyclic, star, and injective colouring: bounding the diameter
- On the minimum sum coloring of \(P_4\)-sparse graphs
- Spy game: FPT-algorithm, hardness and graph products
- Spy game: FPT-algorithm and results on graph products
- Title not available (Why is that?)
- Graphs with few \(P_4\)'s under the convexity of paths of order three
- PSPACE-completeness of two graph coloring games
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)
