Chromatic symmetric functions and H-free graphs | Graphs and Combinatorics
Skip to main content
Springer Nature Link
Log in

Chromatic symmetric functions and H-free graphs

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

Abstract

Using a graph and its colorings we can define a chromatic symmetric function. Stanley’s celebrated conjecture about the e-positivity of claw-free incomparability graphs has seen several related results, including one showing (\(claw, P_4\))-free graphs are e-positive. Here we extend the claw-free idea to general graphs and consider the e-positivity question for H-free graphs where \(H = \{claw, F\}\) and \(H=\){claw, F, co-F}, where F is a four-vertex graph. We settle the question for all cases except \(H=\){claw, co-diamond}, and we provide some partial results in that case.

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

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

Similar content being viewed by others

References

  1. Cho, S., van Willigenburg, S.: Chromatic bases for symmetric functions. Electron. J. Combin. 23(1), P1.15 (2016)

    MathSciNet  MATH  Google Scholar 

  2. Foley, A.M., Hoang, C.T., Merkel, O.D.: Classes of clawfree graphs with \(e\)-positive chromatic symmetric function. arXiv:1808.03391, (2018)

  3. Gasharov, V.: Incomparability graphs of \((3+1)\)-free posets are s-positive. Disc. Math. 157, 193–197 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  4. Goulden, I.P., Jackson, D.M.: Immanants of combinatorial matrices. J. Algebra 148, 305–324 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  5. Greene, C.: Proof of a conjecture on immanants of the Jacobi-Trudi matrix. Linear Algebra Appl. 171, 65–79 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  6. Guay-Paquet, M.: A modular relation for the chromatic symmetric function of \((3+1)\)-posets, arXiv:1306.2400, (2013)

  7. Lozin, V.V., Malyshev, D.S.: Vertex coloring of graphs with few obstructions. Disc. Appl. Math. 216, 273–280 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  8. Olariu, S.: Paw-free graphs. Inf. Proc. Lett. 28, 53–54 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  9. Stanley, R.P.: A symmetric function generalization of the chromatic polynomial of a graph. Adv. Math. 111, 166–194 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  10. Stanley, R.P.: Graph colorings and related symmetric functions: ideas and applications. Disc. Math. 193, 267–286 (1998)

    Article  MATH  Google Scholar 

  11. Stanley, R.P.: Enumerative Combinatorics, vol. 2. Cambridge University Press, Cambridge (1999)

    Book  MATH  Google Scholar 

  12. Stanley, R.P., Stembridge, J.R.: On immanants of Jacobi-Trudi Matrices and permutations with restricted position. JCTA 62, 261–279 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  13. Tsujie, S.: The chromatic symmetric functions of trivially perfect graphs and cographs. Graphs Comb. 34, 1037–1048 (2018)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This work was supported by the Canadian Tri-Council Research Support Fund. The 1st and 2nd authors (A.M. Hamel and C.T. Hoàng) were each supported by individual NSERC Discovery Grants. The 3rd author (J.E. Tuero) was supported by an NSERC Undergraduate Student Research Award (USRA).

Author information

Authors and Affiliations

  1. Department of Physics and Computer Science, Wilfrid Laurier University, Waterloo, ON, Canada

    Angèle M. Hamel, Chính T. Hoàng & Jake E. Tuero

Authors
  1. Angèle M. Hamel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chính T. Hoàng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jake E. Tuero
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Angèle M. Hamel.

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

Hamel, A.M., Hoàng, C.T. & Tuero, J.E. Chromatic symmetric functions and H-free graphs. Graphs and Combinatorics 35, 815–825 (2019). https://doi.org/10.1007/s00373-019-02034-1

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-019-02034-1

Keywords

Search

Navigation