Summary: The claw is the graph \(K_{1,3}\), and the fork is the graph obtained from the claw \(K_{1,3}\) by subdividing one of its edges once. In this paper, we prove a structure theorem for the class of (claw, \(C_4)\)-free graphs that are not quasi-line graphs, and a structure theorem for the class of (fork, \(C_4)\)-free graphs that uses the class of (claw, \(C_4)\)-free graphs as a basic class. Finally, we show that every (fork, \(C_4\))-free graph \(G\) satisfies \(\chi(G)\leqslant \bigg\lceil\frac{3\omega(G)}{2}\bigg\rceil\) via these structure theorems with some additional work on coloring basic classes.
- Claw-free graphs. VI: Colouring
- Coloring quasi-line graphs
- Excluding the fork and antifork
- scientific article; zbMATH DE number 3747156 (Why is no real title available?)
- scientific article; zbMATH DE number 4183452 (Why is no real title available?)
- On the chromatic number of \(2 K_2\)-free graphs
- Radius two trees specify χ‐bounded classes
- Sur le coloriage des graphs
- The Ramsey number R(3, t) has order of magnitude t2/log t
- The structure of claw-free graphs
- Vertex colouring and forbidden subgraphs -- a survey
- On a class of square-free graphs
- Coloring graph classes with no induced fork via perfect divisibility
- Excluding the fork and antifork
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- Square-Free Graphs with No Six-Vertex Induced Path
- Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs
- Perfect divisibility and coloring of some fork-free graphs
- \( \chi \)-binding function for \((C_4, t\text{-broom}^+)\)-free graphs
- Structure and linear-Pollyanna for some square-free graphs
- Trisimplicial vertices in (fork, odd parachute)-free graphs
- Perfect divisibility and coloring in fork-free graphs
- Nearly optimal coloring of some C₄-free graphs
This page was built for publication: Square-free graphs with no induced fork
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q831350)
