Coloring quasi-line graphs

Maria Chudnovsky; Alexandra Ovetsky

doi:10.1002/jgt.20192

Coloring quasi-line graphs

Maria Chudnovsky, Alexandra Ovetsky

Mathematics

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

29 Scopus citations

Abstract

A graph G is a quasi-line graph if for every vertex v, the set of neighbors of v can be expressed as the union of two cliques. The class of quasi-line graphs is a proper superset of the class of line graphs. A theorem of Shannon's implies that if G is a line graph, then it can be properly colored using no more than 3/2ω(G) colors, where ω(G) is the size of the largest clique in G. In this article, we extend this result to all quasi-line graphs. We also Show that this bound is tight.

Original language	English (US)
Pages (from-to)	41-50
Number of pages	10
Journal	Journal of Graph Theory
Volume	54
Issue number	1
DOIs	https://doi.org/10.1002/jgt.20192
State	Published - Jan 2007

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Geometry and Topology

Keywords

Claw-free graphs
Coloring
Quasi-line graphs

Access to Document

10.1002/jgt.20192

Cite this

@article{3b42084e554c457794fe56f40cc3e2b6,

title = "Coloring quasi-line graphs",

abstract = "A graph G is a quasi-line graph if for every vertex v, the set of neighbors of v can be expressed as the union of two cliques. The class of quasi-line graphs is a proper superset of the class of line graphs. A theorem of Shannon's implies that if G is a line graph, then it can be properly colored using no more than 3/2ω(G) colors, where ω(G) is the size of the largest clique in G. In this article, we extend this result to all quasi-line graphs. We also Show that this bound is tight.",

keywords = "Claw-free graphs, Coloring, Quasi-line graphs",

author = "Maria Chudnovsky and Alexandra Ovetsky",

year = "2007",

month = jan,

doi = "10.1002/jgt.20192",

language = "English (US)",

volume = "54",

pages = "41--50",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - Coloring quasi-line graphs

AU - Chudnovsky, Maria

AU - Ovetsky, Alexandra

PY - 2007/1

Y1 - 2007/1

N2 - A graph G is a quasi-line graph if for every vertex v, the set of neighbors of v can be expressed as the union of two cliques. The class of quasi-line graphs is a proper superset of the class of line graphs. A theorem of Shannon's implies that if G is a line graph, then it can be properly colored using no more than 3/2ω(G) colors, where ω(G) is the size of the largest clique in G. In this article, we extend this result to all quasi-line graphs. We also Show that this bound is tight.

AB - A graph G is a quasi-line graph if for every vertex v, the set of neighbors of v can be expressed as the union of two cliques. The class of quasi-line graphs is a proper superset of the class of line graphs. A theorem of Shannon's implies that if G is a line graph, then it can be properly colored using no more than 3/2ω(G) colors, where ω(G) is the size of the largest clique in G. In this article, we extend this result to all quasi-line graphs. We also Show that this bound is tight.

KW - Claw-free graphs

KW - Coloring

KW - Quasi-line graphs

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

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

U2 - 10.1002/jgt.20192

DO - 10.1002/jgt.20192

M3 - Article

AN - SCOPUS:33846466571

SN - 0364-9024

VL - 54

SP - 41

EP - 50

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

Coloring quasi-line graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this