Geodesic
Square-free graphs with no induced fork
The electronic journal of combinatorics, Tome 28 (2021) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 \lceil\frac{3\omega(G)}{2}\rceil$ via these structure theorems with some additional work on coloring basic classes.
DOI : 10.37236/9144
Classification : 05C15, 05C60
Mots-clés : forbidden induced subgraph, graph structure, fork, antifork

Maria Chudnovsky    ; Shenwei Huang  1   ; T. Karthick    ; Jenny Kaufmann 

1 Nankai University 
@article{10_37236_9144,
     author = {Maria Chudnovsky and Shenwei Huang and T. Karthick and Jenny Kaufmann},
     title = {Square-free graphs with no induced fork},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {2},
     doi = {10.37236/9144},
     zbl = {1464.05146},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9144/}
}
TY  - JOUR
AU  - Maria Chudnovsky
AU  - Shenwei Huang
AU  - T. Karthick
AU  - Jenny Kaufmann
TI  - Square-free graphs with no induced fork
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9144/
DO  - 10.37236/9144
ID  - 10_37236_9144
ER  - 
%0 Journal Article
%A Maria Chudnovsky
%A Shenwei Huang
%A T. Karthick
%A Jenny Kaufmann
%T Square-free graphs with no induced fork
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/9144/
%R 10.37236/9144
%F 10_37236_9144
Maria Chudnovsky; Shenwei Huang; T. Karthick; Jenny Kaufmann. Square-free graphs with no induced fork. The electronic journal of combinatorics, Tome 28 (2021) no. 2. doi: 10.37236/9144

Cité par Sources :