Even pairs in Berge graphs with no balanced skew-partitions

Tara Abrishami; Maria Chudnovsky; Yaqian Tang

doi:10.1016/j.disc.2024.114388

Even pairs in Berge graphs with no balanced skew-partitions

Tara Abrishami, Maria Chudnovsky, Yaqian Tang

Mathematics

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

Abstract

Let G be a Berge graph that has no odd prism and no antihole of length at least six as an induced subgraph. We show that every such graph G with no balanced skew-partition is either complete or has an even pair.

Original language	English (US)
Article number	114388
Journal	Discrete Mathematics
Volume	348
Issue number	5
DOIs	https://doi.org/10.1016/j.disc.2024.114388
State	Published - May 2025

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Keywords

Berge graphs
Coloring
Even pairs
Induced subgraphs

Access to Document

10.1016/j.disc.2024.114388

Cite this

@article{6ab4f39c5fef4968922a3aca1c91ce8d,

title = "Even pairs in Berge graphs with no balanced skew-partitions",

abstract = "Let G be a Berge graph that has no odd prism and no antihole of length at least six as an induced subgraph. We show that every such graph G with no balanced skew-partition is either complete or has an even pair.",

keywords = "Berge graphs, Coloring, Even pairs, Induced subgraphs",

author = "Tara Abrishami and Maria Chudnovsky and Yaqian Tang",

note = "Publisher Copyright: {\textcopyright} 2025 Elsevier B.V.",

year = "2025",

month = may,

doi = "10.1016/j.disc.2024.114388",

language = "English (US)",

volume = "348",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Even pairs in Berge graphs with no balanced skew-partitions

AU - Abrishami, Tara

AU - Chudnovsky, Maria

AU - Tang, Yaqian

PY - 2025/5

Y1 - 2025/5

N2 - Let G be a Berge graph that has no odd prism and no antihole of length at least six as an induced subgraph. We show that every such graph G with no balanced skew-partition is either complete or has an even pair.

AB - Let G be a Berge graph that has no odd prism and no antihole of length at least six as an induced subgraph. We show that every such graph G with no balanced skew-partition is either complete or has an even pair.

KW - Berge graphs

KW - Coloring

KW - Even pairs

KW - Induced subgraphs

UR - http://www.scopus.com/inward/record.url?scp=85214523128&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85214523128&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2024.114388

DO - 10.1016/j.disc.2024.114388

M3 - Article

AN - SCOPUS:85214523128

SN - 0012-365X

VL - 348

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 5

M1 - 114388

ER -

Even pairs in Berge graphs with no balanced skew-partitions

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this