Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Structure of some ( P 7, C 4)-free graphs with application to colorings

Published: 18 November 2024 Publication History

Abstract

We use P t and C t to denote a path and a cycle on t vertices, respectively. A diamond is a graph obtained from two triangles that share exactly one edge. A kite is a graph that consists of a diamond and another vertex adjacent to a vertex of degree 2 of the diamond. A gem is a graph that consists of a P 4 plus a vertex adjacent to all vertices of the P 4. Choudum et al. (2021) proved that every (P 7, C 7, C 4, gem)-free graph has either a clique cutset or a vertex whose neighbors is the union of two cliques unless it is a clique blowup of the Petersen graph, and every non-Petersen (P 7, C 7, C 4, diamond)-free graph has either a clique cutset or has a vertex of degree at most max { 2, ω ( G ) − 1 }. In this paper, we extend these two results respectively to (P 7, C 4, gem)-free graphs and (P 7, C 4, diamond)-free graphs. We also prove that if G is a (P 7, C 4, kite)-free graph with δ ( G ) ≤ ω ( G ) and without clique cutsets, then there is an integer ℓ ≥ 0 such that G = K ℓ + H, where H is either the Petersen graph or a well-defined graph F. This implies a polynomial algorithm which can determine the chromatic number of (P 7, C 4, diamond)-free graphs, color (P 7, C 4, kite)-free graphs G with ( ω ( G ) + 1 ) colors, and color (P 7, C 4, gem)-free graphs G with ( 2 ω ( G ) − 1 ) colors.

References

[1]
Bondy J.A., Murty U.S.R., Graph Theory, Springer, New York, 2008.
[2]
Cameron K., Huang S., Merkel O., An optimal χ-bound for (P 6 diamond)-free graphs, J. Graph Theory 97 (2021) 451–465.
[3]
Cameron K., Huang S., Penev I., Sivaraman V., The class of (( P 7, C 4, C 5 ))-free graphs: decomposition, algorithms, and χ-boundedness, J. Graph Theory 93 (2020) 503–552.
[4]
Choudum S.A., Karthick T., Belavadi M.M., Structural domination and coloring of some (( P 7, C 7 ))-free graphs, Discrete Math. 344 (2021).
[5]
Choudum S.A., Karthick T., Shalu M.A., Perfect coloring and linearly χ-bound P 6 -free graphs, J. Graph Theory 54 (2007) 293–306.
[6]
Fraser D.J., Hamel A.M., Hoáng C.T., On the structure of (even-hole,kite)-free graphs, Graphs Combin. 34 (2018) 989–999.
[7]
Gaspers S., Huang S., Linearly χ-bounding ( P 6, C 4 ) -free graphs, in: International Workshop on Graph-Theoretic Concepts in Computer Science, Springer, Cham, 2017.
[8]
Geißer M., Colourings of P 5-Free Graphs, (Ph. D. Thesis) Technische Universität Bergakademie Freiberg, 2022.
[9]
Gravier S., Hoáng C.T., Maffray F., Coloring the hypergraph of maximal cliques of a graph with no long path, Discrete Math. 272 (2003) 285–290.
[10]
Gyárfás A., On Ramsey covering-numbers, Infinite Finite Sets 2 (1975) 801–816.
[11]
Huang S., The optimal χ-bound for ( P 7, C 4, C 5 )-free graphs, 2022, arXiv:2212.05239.
[12]
Karthick T., Maffray F., Square-free graphs with no six-vertex induced path, SIAM J. Discrete Math. 33 (2019) 874–909.
[13]
Lan K., Zhou Y., Liu F., The chromatic number of (P 6, C 4, diamond)-free graphs, Bull. Aust. Math. Soc. (2022) 1–10.
[14]
Mishra S., On graphs with no induced bull and no induced diamond, 2021, arXiv:2107.03750.
[15]
Randerath B., The Vizing bound for the Chromatic Number Based on Forbidden Pairs, (Ph. D. Thesis) Shaker Verlag, Aachen, 1998.
[16]
Randerath B., Schiermeyer I., Vertex colouring and forbidden subgraphs-A survey, Graphs Combin. 20 (2004) 1–40.
[17]
I. Schiermeyer, Polynomial χ-binding functions for P 5-free graphs, personal communication.
[18]
Schiermeyer I., Chromatic number of P 5-free graphs: Reed’s conjecture, Discrete Math. 339 (2016) 1940–1943.
[19]
Schiermeyer I., Randerath B., Polynomial χ-binding functions and forbidden induced subgraphs: A survey, Graphs Combin. 35 (2019) 1–31.
[20]
Scott A., Seymour P., A survey of χ-boundedness, J. Graph Theory 95 (2020) 473–504.
[21]
Scott A., Seymour P., Spirkl S., Polynomial bounds for chromatic number iv: a near-polynomial bound for excluding the five-vertex path, Combinatorica 43 (2023) 845–852.
[22]
Seinsche D., On a property of the class of n-colorable graphs, J. Comb. Theory Ser. B 16 (1974) 191–193.
[23]
Tarjan R.E., Decomposition by clique separators, Discrete Math. 55 (1985) 221–232.

Index Terms

  1. Structure of some ( P 7, C 4)-free graphs with application to colorings
              Index terms have been assigned to the content through auto-classification.

              Recommendations

              Comments

              Please enable JavaScript to view thecomments powered by Disqus.

              Information & Contributors

              Information

              Published In

              cover image Discrete Applied Mathematics
              Discrete Applied Mathematics  Volume 357, Issue C
              Nov 2024
              465 pages

              Publisher

              Elsevier Science Publishers B. V.

              Netherlands

              Publication History

              Published: 18 November 2024

              Author Tags

              1. P7 -free graphs
              2. Chromatic number
              3. Clique number

              Qualifiers

              • Research-article

              Contributors

              Other Metrics

              Bibliometrics & Citations

              Bibliometrics

              Article Metrics

              • 0
                Total Citations
              • 0
                Total Downloads
              • Downloads (Last 12 months)0
              • Downloads (Last 6 weeks)0
              Reflects downloads up to 08 Dec 2024

              Other Metrics

              Citations

              View Options

              View options

              Login options

              Media

              Figures

              Other

              Tables

              Share

              Share

              Share this Publication link

              Share on social media