[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

On the b-Continuity of the Lexicographic Product of Graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to each other color class. The b-chromatic number of G is the maximum integer \(\chi _b(G)\) for which G has a b-coloring with \(\chi _b(G)\) colors. A graph G is b-continuous if G has a b-coloring with k colors, for every integer k in the interval \([\chi (G),\chi _b(G)]\). It is known that not all graphs are b-continuous. Here, we investigate whether the lexicographic product G[H] of b-continuous graphs G and H is also b-continuous. Using homomorphisms, we provide a new lower bound for \(\chi _b(G[H])\), namely \(\chi _b(G[K_t])\), where \(t=\chi _b(H)\), and prove that if \(G[K_\ell ]\) is b-continuous for every positive integer \(\ell \), then G[H] admits a b-coloring with k colors, for every k in the interval \([\chi (G[H]),\chi _b(G[K_t])]\). We also prove that \(G[K_\ell ]\) is b-continuous, for every positive integer \(\ell \), whenever G is a \(P_4\)-sparse graph, and we give further results on the b-spectrum of \(G[K_\ell ]\), when G is chordal. Finally, we determine the value of \(\chi _b(T[K_\ell ])\), when T is a tree.

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
£29.99 /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 (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. The graph terminology used in this paper follows [5].

References

  1. Allkhateeb, M., Kohl, A.: Upper bounds on the b-chromatic number and results for restricted graph classes. Discuss. Math. Graph Theory 31(4), 709–735 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  2. Balakrishnan, R., Kavaskar, T.: b-Coloring of Kneser graphs. Discret. Appl. Math. 160, 9–14 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  3. Barth, D., Cohen, J., Faik, T.: Complexity of determining the b-continuity property of graphs. Technical Report PRiSM Technical Report 2003/37, Université de Versailles (2003)

  4. Barth, D., Cohen, J., Faik, T.: On the b-continuity property of graphs. Discret. Appl. Math. 155(13), 1761–1768 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  5. Bondy, A., Murty, U.S.R.: Graph Theory. Springer, Berlin (2008)

    Book  MATH  Google Scholar 

  6. Bonomo, F., Durán, G., Maffray, F., Marenco, J., Valencia-Pabon, M.: On the \(b\)-coloring of cographs and \(p_4\)-sparse graphs. Graphs Comb. 25, 153–167 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  7. Campos, V., Lima, C., Martins, N.A., Sampaio, L., Santos, M.C., Silva, A.: The b-chromatic index of graphs. Discret. Math. 338, 2072–2079 (2015)

    Article  MATH  Google Scholar 

  8. Campos, V., Lima, C., Silva, A.: Graphs of girth at least 7 have high b-chromatic number. Eur. J. Comb. 48, 154–164 (2015)

    Article  MATH  MathSciNet  Google Scholar 

  9. Chow, F., Hennessy, J.: Register allocation by priority-based coloring. ACM SIGPLAN Not. 19, 222–232 (1984)

    Article  Google Scholar 

  10. Chow, F., Hennessy, J.: The priority-based coloring approach to register allocation. ACM Trans. Progr. Lang. Syst. 12, 501–536 (1990)

    Article  Google Scholar 

  11. Faik, T.: About the b-continuity of graphs. In: Workshop on Graphs and Combinatorial Optimization, vol. 17, pp. 151–156 (2004)

  12. Faik, T., Sacle, J.F.: Some b-continuous classes of graph. Technical report, CNRS-Université Paris Sud-LRI (2003)

  13. Fulkerson, D.R., Gross, O.: Incidence matrices and interval graphs. Pac. J. Math. 15, 835–855 (1965)

    Article  MATH  MathSciNet  Google Scholar 

  14. Gamst, A.: Some lower bounds for the class of frequency assignment problems. IEEE Trans. Veh. Technol. 35, 8–14 (1986)

    Article  Google Scholar 

  15. Geller, D., Stahl, S.: The chromatic number and other functions of the lexicographic product. J. Comb. Theory B 19, 87–95 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  16. Havet, F., Sales, C.L., Sampaio, L.: \(b\)-Coloring of tight graphs. Discret. Appl. Math. 160(18), 2709–2715 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  17. Hell, P., Nesetril, J.: Graphs and Homomorphisms. Oxford University Press, Oxford (2004)

    Book  MATH  Google Scholar 

  18. Hoàng, C.: Perfect graphs. Ph.D. thesis, School of Computer Science, McGill University, Montreal (1995)

  19. Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718–720 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  20. Håstad, J.: Clique is hard to approximate within \(n^{1 - \epsilon }\). Acta Mathematica 182(1), 105–142 (1999)

    Article  MathSciNet  Google Scholar 

  21. Irving, R.W., Manlove, D.F.: The b-chromatic number of a graph. Discret. Appl. Math. 91(1–3), 127–141 (1999)

    Article  MATH  Google Scholar 

  22. Jakovac, M., Peterin, I.: On the b-chromatic number of some graph products. Stud. Sci. Math. Hung. 49(2), 156–169 (2012)

    MATH  MathSciNet  Google Scholar 

  23. Jamison, B., Olariu, S.: Linear time optimization algorithms for p4-sparse graphs. Discret. Appl. Math. 61(2), 155–175 (1995)

    Article  MATH  Google Scholar 

  24. Javadi, R., Omoomi, B.: On b-coloring of the Kneser graphs. Discret. Math. 309(13), 4399–4408 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  25. Kára, J., Kratochvíl, J., Voigt, M.: b-continuity. Technical report, Technical University Ilmenau, Faculty of Mathematics and Natural Sciences (2004)

  26. Kratochvíl, J., Tuza, Z., Voigt, M.: On the \(b\)-chromatic number of graphs. In: Kuc̆era, L. (ed.) Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science, vol. 2573, pp. 310–320. Springer, Berlin (2002)

  27. Saad, Y.: Iterative Methods for Sparse Linear Systems. PWS Publishing Company, Boston (1996)

    MATH  Google Scholar 

  28. Sales, C.L., Vargas, R., Sampaio, L.: b-continuity and the lexicographic product of graphs. Electron. Notes Discrete Math. 50, 139–144 (2015). doi:10.1016/j.endm.2015.07.024

  29. Sales, C.L., Silva, A.: The b-continuity of graphs with large girth. Graphs. Comb. (2017). doi:10.1007/s00373-017-1828-x

  30. Velasquez, C.I.B., Bonomo, F., Koch, I.: On the b-coloring of p4-tidy graphs. Discret. Appl. Math. 159(1), 60–68 (2011)

    Article  MATH  Google Scholar 

  31. Werra, D.: An introduction to timetabling. Eur. J. Oper. Res. 19, 151–161 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  32. Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(6), 103–128 (2007). doi:10.4086/toc.2007.v003a006

Download references

Author information

Authors and Affiliations

  1. Departamento de Computação, Universidade Federal do Ceará, Av. Mister Hull, s/n - Pici, Fortaleza, CE, CEP 60455-760, Brazil

    Cláudia Linhares Sales

  2. Centro de Ciências, Universidade Estadual do Ceará, Av. Dr. Silas Munguba, 1700, Campus do Itaperi, Fortaleza, CE, CEP 60714-903, Brazil

    Leonardo Sampaio

  3. Departamento de Matemática, Universidade Federal do Ceará, Av. Mister Hull, s/n - Pici, Fortaleza, CE, CEP 60455-760, Brazil

    Ana Silva

Authors
  1. Cláudia Linhares Sales
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Leonardo Sampaio
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ana Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ana Silva.

Additional information

All authors are members of the ParGO Research Group: Parallelism, Graphs and Optimization.

This work was partially supported by CNPq and CAPES, Brazil.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Linhares Sales, C., Sampaio, L. & Silva, A. On the b-Continuity of the Lexicographic Product of Graphs. Graphs and Combinatorics 33, 1165–1180 (2017). https://doi.org/10.1007/s00373-017-1832-1

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-017-1832-1

Keywords

Search

Navigation