The χ-Boundedness of P2∪P3-Free Graphs
In the early 1980s, Gyárfás introduced the concept of the χ-bound with χ-binding functions thereby extending the notion of perfectness. There are a number of challenging conjectures about the χ-bound. Let χG, ωG, and ΔG be the chromatic number, clique number, and maximum degree of a graph G, respect...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2022-01-01
|
| Series: | Journal of Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2022/2071887 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832554960146923520 |
|---|---|
| author | Xiao Wang Donghan Zhang |
| author_facet | Xiao Wang Donghan Zhang |
| author_sort | Xiao Wang |
| collection | DOAJ |
| description | In the early 1980s, Gyárfás introduced the concept of the χ-bound with χ-binding functions thereby extending the notion of perfectness. There are a number of challenging conjectures about the χ-bound. Let χG, ωG, and ΔG be the chromatic number, clique number, and maximum degree of a graph G, respectively. In this paper, we prove that if G is a triangle-free and P2∪P3-free graph, then χG≤3 unless G is one of eight graphs with ΔG=5 and χG=4, where the eight graphs are extended from the Grötzsch graph as a Mycielskian of a 5-cycle graph. Moreover, we also show that χG≤3ωG if G is a P2∪P3,W4-free graph. |
| format | Article |
| id | doaj-art-517b6f75d1ae48f29bfcd791ad60b5a7 |
| institution | Kabale University |
| issn | 2314-4785 |
| language | English |
| publishDate | 2022-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Mathematics |
| spelling | doaj-art-517b6f75d1ae48f29bfcd791ad60b5a72025-02-03T05:50:00ZengWileyJournal of Mathematics2314-47852022-01-01202210.1155/2022/2071887The χ-Boundedness of P2∪P3-Free GraphsXiao Wang0Donghan Zhang1College of Mathematics and Computer ApplicationCollege of Mathematics and Computer ApplicationIn the early 1980s, Gyárfás introduced the concept of the χ-bound with χ-binding functions thereby extending the notion of perfectness. There are a number of challenging conjectures about the χ-bound. Let χG, ωG, and ΔG be the chromatic number, clique number, and maximum degree of a graph G, respectively. In this paper, we prove that if G is a triangle-free and P2∪P3-free graph, then χG≤3 unless G is one of eight graphs with ΔG=5 and χG=4, where the eight graphs are extended from the Grötzsch graph as a Mycielskian of a 5-cycle graph. Moreover, we also show that χG≤3ωG if G is a P2∪P3,W4-free graph.http://dx.doi.org/10.1155/2022/2071887 |
| spellingShingle | Xiao Wang Donghan Zhang The χ-Boundedness of P2∪P3-Free Graphs Journal of Mathematics |
| title | The χ-Boundedness of P2∪P3-Free Graphs |
| title_full | The χ-Boundedness of P2∪P3-Free Graphs |
| title_fullStr | The χ-Boundedness of P2∪P3-Free Graphs |
| title_full_unstemmed | The χ-Boundedness of P2∪P3-Free Graphs |
| title_short | The χ-Boundedness of P2∪P3-Free Graphs |
| title_sort | χ boundedness of p2∪p3 free graphs |
| url | http://dx.doi.org/10.1155/2022/2071887 |
| work_keys_str_mv | AT xiaowang thechboundednessofp2p3freegraphs AT donghanzhang thechboundednessofp2p3freegraphs AT xiaowang chboundednessofp2p3freegraphs AT donghanzhang chboundednessofp2p3freegraphs |