Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On Indicated Coloring of Some Classes of Graphs

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

Abstract

Indicated coloring is a type of game coloring in which two players collectively color the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent the realization of this project. The smallest number of colors necessary for Ann to win the game on a graph G (regardless of Ben’s strategy) is called the indicated chromatic number of G, denoted by \(\chi _i(G)\). In this paper, we obtain structural characterization of \(\{P_5,K_4,Kite,Bull\}\)-free graphs and connected \(\{P_6,C_5, K_{1,3}\}\)-free graphs that contain an induced \(C_6\). Also, we prove that \(\{P_5,K_4,Kite,Bull\}\)-free graphs and connected \(\{P_6,C_5,\overline{P_5}, K_{1,3}\}\)-free graphs which contain an induced \(C_6\) are k-indicated colorable for all \(k\ge \chi (G)\). In addition, we show that, if \(m\ge 1\) and G is a bipartite graph, then \(\chi _i(\mathbb {K}[G](m,m,\ldots ,m))=\chi (\mathbb {K}[G](m,m,\ldots ,m))\). Further, we show that \(\mathbb {K}[C_5]\) is k-indicated colorable for all \(k\ge \chi (G)\) and as a consequence, we exhibit that \(\{P_2\cup P_3, C_4\}\)-free graphs, \(\{P_5,C_4\}\)-free graphs are k-indicated colorable for all \(k\ge \chi (G)\). This partially answers one of the questions which was raised by Grzesik (Discret Math 312:3467–3472, 2012).

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Aravind, N.R., Karthick, T., Subramanian, C.R.: Bounding \(\chi \) in terms of \(\omega \) and \(\Delta \) for some classes of graphs. Discret. Math. 311, 911–920 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bacsó, G., Tuza, Z.: Dominating cliques in \(P_5\)-free graphs. Period. Math. Hung. 21, 303–308 (1990)

    Article  MATH  Google Scholar 

  3. Bohman, T., Frieze, A., Sudakov, B.: The game chromatic number of random graphs. Random Struct. Algorithms 32, 223–235 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  4. Brandstädt, A., Mosca, R.: On the structure and stability number of \(P_5\)- and co-chair-free graphs. Discret. Appl. Math. 132, 47–65 (2004)

    Article  MATH  Google Scholar 

  5. Choudum, S.A., Karthick, T.: Maximal cliques in \(\{P_2\cup P_3, C_4\}\)-free graphs. Discret. Math. 310, 3398–3403 (2010)

    Article  MATH  Google Scholar 

  6. Esperet, L., Lemoine, L., Maffray, F., Morel, G.: The chromatic number of \(\{P_5, K_4\}\)-free graphs. Discret. Math. 313, 743–754 (2013)

    Article  MATH  Google Scholar 

  7. Fouquet, J.L., Giakoumakis, V., Maire, F., Thuillier, H.: On graphs without \(P_5\) and \(\overline{P_5}\). Discret. Math. 146, 33–44 (1995)

    Article  MATH  Google Scholar 

  8. Francis Raj, S., Pandiya Raj, R., Patil, H.P.: On indicated chromatic number of graphs. Graphs Comb. 33, 203–219 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  9. Grzesik, A.: Indicated coloring of graphs. Discret. Math. 312, 3467–3472 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  10. Guan, D., Zhu, X.: The game chromatic number of outerplanar graphs. J. Graph Theory 30, 67–70 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  11. Hof, P.V., Paulusma, D.: A new characterization of \(P_6\)-free graphs. Discret. Appl. Math. 158, 731–740 (2010)

    Article  MATH  Google Scholar 

  12. Lasoń, M.: Indicated coloring of matroids. Discret. Appl. Math. 179, 241–243 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  13. Liu, J., Peng, Y., Zhao, C.: Characterization of \(P_6\)-free graphs. Discret. Appl. Math. 155, 1038–1043 (2007)

    Article  MATH  Google Scholar 

  14. Pandiya Raj, R., Francis Raj, S., Patil, H.P.: On indicated coloring of graphs. Graphs Comb. 31, 2357–2367 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  15. Randerath, B., Schiermeyer, I.: 3-colorability \(\in P\) for \(P_6\)-free graphs. Discret. Appl. Math. 136, 299–313 (2004)

    Article  MATH  Google Scholar 

  16. Sekiguchi, Y.: The game coloring number of planar graphs with a given girth. Discret. Math. 330, 11–16 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  17. Sumner, D.P.: Subtrees of a graph chromatic number. In: Chartrand, G. (ed.) The Theory and Applications of Graphs. Wiley, New York (1981)

    Google Scholar 

  18. West, D.B.: Introduction to Graph Theory, vol. 2. Prentice-Hall, Englewood Cliffs (2000)

    Google Scholar 

  19. Wu, J., Zhu, X.: Lower bounds for the game colouring number of partial \(k\)-trees and planar graphs. Discret. Math. 308, 2637–2642 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  20. Zhu, X.: The game coloring number of planar graphs. J. Comb. Theory Ser. B 75, 245–258 (1999)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors thank the referee for his or her very useful suggestions and comments which helped in the betterment of the paper. For the first author, this research was supported by the Council of Scientific and Industrial Research, Government of India, File no: 09/559(0096)/2012-EMR-I. For the second author, this research was supported by SERB DST Project, Government of India, File no: EMR/ 2016/007339. Also, for the third author, this research was supported by the UGC-Basic Scientific Research, Government of India, Login id: gokulnath.res@pondiuni.edu.in.

Author information

Authors and Affiliations

  1. Department of Mathematics, Pondicherry University, Puducherry, 605014, India

    P. Francis, S. Francis Raj & M. Gokulnath

Authors
  1. P. Francis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. Francis Raj
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. Gokulnath
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S. Francis Raj.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Francis, P., Francis Raj, S. & Gokulnath, M. On Indicated Coloring of Some Classes of Graphs. Graphs and Combinatorics 35, 1105–1127 (2019). https://doi.org/10.1007/s00373-019-02061-y

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-019-02061-y

Keywords

Mathematics Subject Classification

Search

Navigation