Restricted coloring problems on Graphs with few P 4’s | Annals of Operations Research Skip to main content
Springer Nature Link
Log in

Restricted coloring problems on Graphs with few P 4’s

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

In this paper, we obtain linear time algorithms to determine the acyclic chromatic number, the star chromatic number, the non repetitive chromatic number and the clique chromatic number of P 4-tidy graphs and (q, q − 4)-graphs, for every fixed q, which are the graphs such that every set with at most q vertices induces at most q − 4 distinct P 4’s. These classes include cographs and P 4-sparse graphs. We also obtain a linear time algorithm to compute the harmonious chromatic number of connected P 4-tidy graphs and connected (q, q − 4)-graphs. All these coloring problems are known to be NP-hard for general graphs. These algorithms are fixed parameter tractable on the parameter q(G), which is the minimum q such that G is a (q, q − 4)-graph. We also prove that every connected (q, q − 4)-graph with at least q vertices is 2-clique-colorable and that every acyclic coloring of a cograph is also nonrepetitive, generalizing the main result of Lyons (2011).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Reference

  • Alon, N., Grytczuk, J., Haluszczak, M., & Riordan, O. (2002). Nonrepetitive colorings of graphs. Random Structures and Algorithms, 21(3–4), 336–346.

    Article  Google Scholar 

  • Albertson, M., Chappell , G., Kierstead, H., Kndgen, A., & Ramamurthi, R. (2004). Coloring with no 2-colored P 4’s. The Electronic Journal of Combinatorics 11

  • Asdre, K., Ioannidou, K., & Nikolopoulose, S. (2007). The harmonious coloring problem is NP-complete for interval and permutation graphs. Discrete Applied Mathematics, 155, 2377–2382.

    Article  Google Scholar 

  • Babel, L., & Olariu, S. (1998). On the structure of graphs with few P 4's. Discrete Applied Mathematics, 84, 1–13.

    Article  Google Scholar 

  • Babel, L., Kloks, T., Kratochvíl, J., Kratsch, D., Muller, H., & Olariu, S. (2001). Efficient algorithms for graphs with few P 4′s. Discrete Mathematics, 235, 29–51.

    Article  Google Scholar 

  • Bacsó, G., Gravier, S., Gyárfas, A., Preissman, M., & Sebo, A. (2004). Coloring the maximal cliques of graphs, SIAM Journal on Discrete Algorithms 17. Memoir, 3, 361–376.

    Google Scholar 

  • Barát, J., & Woody, D. (2008). Notes on Nonrepetitive Graph Colouring. The Electronic Journal of Combinatorics 15

  • Baumann, S. (1996). A linear algorithm for the homogeneous decomposition of graphs, Zentrum Mathematik, Technische Universität München, Report No. M-9615

  • Bodlaender, H. L. (1989). Number is NP-complete for cographs and interval graphs. Information Processing Letters, 31, 135–138.

    Article  Google Scholar 

  • Bondy, A., Murty, U. S. R. (2008). Graph theory. London: Springer

    Book  Google Scholar 

  • Bonomo, F., Durán, G., & Marenco, J.(2009). Exploring the complexity boundary between coloring and list-coloring. Annals of Operations Research , 169, 3–16

    Article  Google Scholar 

  • Borodin, O. V. (1979). On acyclic colorings of planar graphs. Discrete Mathematics, 25, 211–236

    Article  Google Scholar 

  • Campbell, D., & Edwards, K. (2004). A new lower bound for the harmonious chromatic number. The Australasian Journal of Combinatorics, 29, 99–102

    Google Scholar 

  • Campos, V., Klein, S., Sampaio, R., & Silva, A. (2011). Two fixed parameter algorithms for the cocoloring problem, ISAAC’11

  • Coleman, T.F., & Cai, J. (1986). The cyclic coloring problem and estimation of sparse Hessian matrices, SIAM Journal on Algebraic and Discrete Methods, 7.Memoir, 2, 221–235.

    Google Scholar 

  • Fertin, G., Raspaud, A., & Reed, B. (2004). Star coloring of graphs, Journal of Graph Theory 47:163–182

    Article  Google Scholar 

  • Giakoumakis, V. (1996). P 4-laden graphs: A new class of brittle graphs. Information Processing Letters, 60, 29–36

    Article  Google Scholar 

  • Giakoumakis, V., Roussel, H., & Thuillier, H. (1997). On P 4-tidy graphs, Discrete Mathematics and Theoretical Computer Science, 1, 17–41

    Google Scholar 

  • Grytczuk, J. (2007). Nonrepetitive colorings of graphs—A survey. International Journal of Mathematics and Mathematical Sciences. doi:10.1155/2007/74639

  • Grytczuk, J. (2008). Thue type problems for graphs, points, and numbers. Discrete Mathematics, 308, 4419–4429.

    Article  Google Scholar 

  • Grytczuk, J., Przybylo, J., & Zhu, X. (2010). Nonrepetitive list colourings of paths. Random Structures and Algorithms, 38, 162–173.

    Google Scholar 

  • Jamison, B., & Olariu, S. (1995). P-components and the homogeneous decomposition of graphs, SIAM Journal on Discrete Mathematics, 8, 448–463

    Article  Google Scholar 

  • Jamison, B., & Olariu, S. (1989). A new class of brittle graphs. Studies in Applied Mathematics, 81, 89–92.

    Google Scholar 

  • Kostochka, A.V. (1978). Upper bounds of chromatic functions of graphs. Doctoral thesis, Novosibirsk (in Russian)

  • Kratochvíl, J., & Tuza, Z. (2002). On the complexity of bicoloring clique hypergraphs of graphs. Journal of Algorithms, 45(1), 40–54.

    Article  Google Scholar 

  • Lyons, A. (2011). Acyclic and star colorings of cographs. Discrete Applied Mathematics, 159, 1842–1850

    Article  Google Scholar 

  • Marx, D., & Schaefer, M. (2009). The complexity of nonrepetitive coloring. Discrete Applied Mathematics, 157, 13–18.

    Article  Google Scholar 

  • Möhring, R. H. (1986). Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and boolean functions. Annals of Operations Research, 4, 195–225

    Google Scholar 

  • Tedder, M., Corneil, D., Habib, M., & Paul, C. (2008) Simpler linear-time modular decomposition via recursive factorizing permutations. Lecture Notes in Computer Science, 5125, 634–645

    Article  Google Scholar 

Download references

Acknowledgment

The authors are partially supported by CNPq and Funcap.

Author information

Authors and Affiliations

  1. Universidade Federal do Ceará, Fortaleza, Brazil

    Cláudia Linhares-Sales, Nicolas Martins & Rudini M. Sampaio

  2. INRIA, Rocquencourt, France

    Ana Karolinna Maia

Authors
  1. Cláudia Linhares-Sales
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Ana Karolinna Maia
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Nicolas Martins
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Rudini M. Sampaio
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Rudini M. Sampaio.

Additional information

The statements of some of the results of this paper appeared in the Proc. of the Latin-American Algorithms, Graphs and Optimization Symposium LAGOS’11.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Linhares-Sales, C., Maia, A.K., Martins, N. et al. Restricted coloring problems on Graphs with few P 4’s. Ann Oper Res 217, 385–397 (2014). https://doi.org/10.1007/s10479-014-1537-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-014-1537-2

Keywords