Coloring of Graphs with no Induced Six-Vertex path

Abstract

Graph coloring is one among the oldest and broadly studied topics in graph theory. A coloring of a graph G is an assignment of colors to the vertices of G such that no two adjacent vertices receive the same color, and the chromatic number of G (denoted by χ(G)) is the minimum number of colors needed to color G. The clique number of G (denoted by ω(G)) is the maximum number of mutually adjacent vertices in G. In this thesis, we focus on some problems on bounding the chromatic number in terms of clique number for certain special classes of graphs with no long induced paths, namely the class of Pt-free graphs, for t ≥ 5. A hereditary class of graphs G is said to be χ-bounded if there exists a function f : N → N with f(1) = 1 and f(x) ≥ x, for all x ∈ N (called a χ-binding function for G) such that χ(G) ≤ f(ω(G)), for each G ∈ G. The smallest χ-binding function f∗ for G is defined as f∗(x) := max{χ(G) : G ∈ G and ω(G) = x}. The class G is called polynomially χ-bounded if it admits a polynomial χ-binding function. An intriguing open question is whether the class of Pt-free graphs is polynomially χ-bounded or not. This problem is open even for t = 5 and seems to be difficult. So researchers are interested in finding (smallest) polynomial χ-binding functions for some subclasses of Pt-free graphs. Here, we explore the structure of some classes of P6-free graphs and obtain (smallest/linear) χ-binding functions for such classes of graphs. Our results generalize/improve several previously known results available in the literature. Chapter 1 consists of a brief introduction on χ-bounded graphs and a short survey on known χ-bounded P6-free graphs. We also provide motivations, algorithmic issues, and relations of χ-boundedness to other well-known/related conjectures in graph theory. In Chapter 2, we study the class of (P2 + P3, P2 + P3)-free graphs, and show that the function f : N → N defined by f(1) = 1, f(2) = 4, and f(x) = max

x + 3, 3x 2

− 1

, for x ≥ 3, is the smallest χ-binding function for the class of (P2 + P3, P2 + P3)-free graphs. In Chapter 3, we are interested in the structure of (P5, 4-wheel)-free graphs, and in coloring of such graphs. Indeed, we first prove that if G is a connected (P5, 4-wheel)-free graph, then either G admits a clique cut-set, or G is a perfect graph, or G is a quasi-line graph, or G has three disjoint stable sets whose union meets each maximum clique of G at least twice and the other maximal cliques of G at least once. Using this result, we prove that every (P5, 4-wheel)-free graph G satisfies χ(G) ≤ 3 2ω(G). We also provide infinitely many (P5, 4-wheel)-free graphs H with χ(H) ≥ 10 7 ω(H). It is known that every (P5,K4)-free graph G satisfies χ(G) ≤ 5, and that the bound is tight. Both the class of (P5, flag)-free graphs and the class of (P5, K5 − e)-free graphs generalize the class of (P5,K4)-free graphs. In Chapter 4, we explore the structure and coloring of (P5, K5 − e)-free graphs. In particular, we prove that if G is a connected (P5,K5 − e)-free graph with ω(G) ≥ 7, then either G is the complement of a bipartite graph or G has a clique cut-set. From this result, we show that if G is a (P5,K5 − e)-free graph with ω(G) ≥ 4, then χ(G) ≤ max{7, ω(G)}. Moreover, the bound is tight when ω(G) /∈ {4, 5, 6}. In Chapter 5, we investigate the coloring of (P5, flag)-free graphs. We prove that every (P5, flag,K5)- free graph G that contains a K4 satisfies χ(G) ≤ 8, every (P5, flag,K6)-free graph G satisfies χ(G) ≤ 8, and that every (P5, flag,K7)-free graph G satisfies χ(G) ≤ 9. Moreover, we prove that every (P5, flag)- free graph G with ω(G) ≥ 4 satisfies χ(G) ≤ max{8, 2ω(G) − 3}, and that the bound is tight for ω(G) ∈ {4, 5, 6}.