TY - JOUR
T1 - Square-free graphs with no induced fork
AU - Chudnovsky, Maria
AU - Huang, Shenwei
AU - Karthick, T.
AU - Kaufmann, Jenny
N1 - Funding Information:
This research is supported by NSF grant DMS-1763817. This material is based upon work supported in part by the U. S. Army Research Laboratory and the U. S. Army Research Office under grant number W911NF-16-1-0404. This research is supported by the National Natural Science Foundation of China (11801284) and Natural Science Foundation of Tianjin (20JCYBJC01190). This research is partially supported by DST-SERB, Government of India under MATRICS scheme (MTR/2018/000288). This work was performed when the author was at Princeton University.
Funding Information:
∗This research is supported by NSF grant DMS-1763817. This material is based upon work supported in part by the U. S. Army Research Laboratory and the U. S. Army Research Office under grant number W911NF-16-1-0404. †The corresponding author. This research is supported by the National Natural Science Foundation of China (11801284) and Natural Science Foundation of Tianjin (20JCYBJC01190). ‡This research is partially supported by DST-SERB, Government of India under MATRICS scheme (MTR/2018/000288). §This work was performed when the author was at Princeton University.
Publisher Copyright:
© The authors.
PY - 2021
Y1 - 2021
N2 - The claw is the graph K1,3, and the fork is the graph obtained from the claw K1,3 by subdividing one of its edges once. In this paper, we prove a structure theorem for the class of (claw, C4)-free graphs that are not quasi-line graphs, and a structure theorem for the class of (fork, C4)-free graphs that uses the class of (claw, C4)-free graphs as a basic class. Finally, we show that every (fork, C4)-free graph G satisfies (formula presented) via these structure theorems with some additional work on coloring basic classes.
AB - The claw is the graph K1,3, and the fork is the graph obtained from the claw K1,3 by subdividing one of its edges once. In this paper, we prove a structure theorem for the class of (claw, C4)-free graphs that are not quasi-line graphs, and a structure theorem for the class of (fork, C4)-free graphs that uses the class of (claw, C4)-free graphs as a basic class. Finally, we show that every (fork, C4)-free graph G satisfies (formula presented) via these structure theorems with some additional work on coloring basic classes.
UR - http://www.scopus.com/inward/record.url?scp=85105363226&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85105363226&partnerID=8YFLogxK
U2 - 10.37236/9144
DO - 10.37236/9144
M3 - Article
AN - SCOPUS:85105363226
SN - 1077-8926
VL - 28
JO - Electronic Journal of Combinatorics
JF - Electronic Journal of Combinatorics
IS - 2
M1 - #P2.20
ER -