Square-free graphs with no induced fork

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

doi:10.37236/9144

Square-free graphs with no induced fork

Maria Chudnovsky, Shenwei Huang, T. Karthick, Jenny Kaufmann

Mathematics

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

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₄)-free graphs that are not quasi-line graphs, and a structure theorem for the class of (fork, C₄)-free graphs that uses the class of (claw, C₄)-free graphs as a basic class. Finally, we show that every (fork, C₄)-free graph G satisfies (formula presented) via these structure theorems with some additional work on coloring basic classes.

Original language	English (US)
Article number	#P2.20
Journal	Electronic Journal of Combinatorics
Volume	28
Issue number	2
DOIs	https://doi.org/10.37236/9144
State	Published - 2021

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.37236/9144

Cite this

@article{54e3fe8a3a7a490cb312bd590ea4a8e8,

title = "Square-free graphs with no induced fork",

abstract = "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.",

author = "Maria Chudnovsky and Shenwei Huang and T. Karthick and Jenny Kaufmann",

note = "Publisher Copyright: {\textcopyright} The authors.",

year = "2021",

doi = "10.37236/9144",

language = "English (US)",

volume = "28",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "2",

}

TY - JOUR

T1 - Square-free graphs with no induced fork

AU - Chudnovsky, Maria

AU - Huang, Shenwei

AU - Karthick, T.

AU - Kaufmann, Jenny

N1 - 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 -

Square-free graphs with no induced fork

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this