Search

A hereditary class G of graphs is χ -bounded if there is a χ -binding function, say f , such that χ (G) ≤ f (ω (G)) , for every G ∈ G , where χ (G) (ω (G)) denotes the chromatic (clique) number of G. A diamond is a graph obtained from K 4 by removing an edge, and a dart is a graph obtained from a diamond by adding a pendent edge to a vertex of degree 3 of the diamond. Gravier, Hoáng and Maffray showed that every (P 6 , K 4)-free graph is 16-colorable (Gravier et al., 2003). Brause and Gei β er showed that (P 5 , dart)-free graphs G have a binding function Θ ( ω 2 (G) log ω (G) ) (Brause and Gei β er, 2021). In this paper, we show that every (P 6 , dart , K 4)-free graph is 7-colorable. [ABSTRACT FROM AUTHOR]

A pentagraph is a graph without cycles of length 3 or 4 and without induced cycles of odd length at least 7, and a heptagraph is one without cycles of length less than 7 and without induced cycles of odd length at least 9. Chudnovsky and Seymour proved that every pentagraph is 3‐colorable. In this paper, we show that every heptagraph is 3‐colorable. [ABSTRACT FROM AUTHOR]

Abstract A hole is an induced cycle of length at least 4, and a cap is obtained from a hole by adding a new vertex and joining it to exactly two adjacent vertices of the hole. Let G be a graph containing neither caps nor holes of even lengths as induced subgraphs. Cameron et al. (2018) showed that χ (G) ≤ ⌊ 3 ω (G) 2 ⌋ , and asked whether χ (G) ≤ ⌈ 5 ω (G) 4 ⌉ , where χ (G) and ω (G) denote the chromatic number and clique number of G , respectively. In this paper, we show that χ (G) ≤ ⌈ 4 ω (G) 3 ⌉ , and χ (G) ≤ ⌈ 5 ω (G) 4 ⌉ if G further has no 5-cycles sharing exactly one edge. This improves the conclusion of Cameron et al. (2018), and conditionally answers their question in affirmative. [ABSTRACT FROM AUTHOR]

Let G be a graph. We say that G is perfectly divisible if for each induced subgraph H of G , V (H) can be partitioned into A and B such that H [ A ] is perfect and ω (H [ B ]) < ω (H). We use P t and C t to denote a path and a cycle on t vertices, respectively. For two disjoint graphs F 1 and F 2 , we use F 1 ∪ F 2 to denote the graph with vertex set V (F 1) ∪ V (F 2) and edge set E (F 1) ∪ E (F 2) , and use F 1 + F 2 to denote the graph with vertex set V (F 1) ∪ V (F 2) and edge set E (F 1) ∪ E (F 2) ∪ { x y | x ∈ V (F 1) and y ∈ V (F 2) }. In this paper, we prove that (i) (P 5 , C 5 , K 2 , 3) -free graphs are perfectly divisible, (ii) χ (G) ≤ 2 ω 2 (G) − ω (G) − 3 if G is (P 5 , K 2 , 3) -free with ω (G) ≥ 2 , (iii) χ (G) ≤ 3 2 (ω 2 (G) − ω (G)) if G is (P 5 , K 1 + 2 K 2) -free, and (iv) χ (G) ≤ 3 ω (G) + 11 if G is (P 5 , K 1 + (K 1 ∪ K 3)) -free. [ABSTRACT FROM AUTHOR]