The Erdo{double acute}s-Lovász Tihany conjecture for quasi-line graphs

József Balogh; Alexandr V. Kostochka; Noah Prince; Michael Stiebitz

doi:10.1016/j.disc.2008.11.016

The Erdo{double acute}s-Lovász Tihany conjecture for quasi-line graphs

József Balogh, Alexandr V. Kostochka, Noah Prince, Michael Stiebitz

Mathematics

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

Abstract

Erdo{double acute}s and Lovász conjectured in 1968 that for every graph G with χ (G) > ω (G) and any two integers s, t ≥ 2 with s + t = χ (G) + 1, there is a partition (S, T) of the vertex set V (G) such that χ (G [S]) ≥ s and χ (G [T]) ≥ t. Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for quasi-line graphs and for graphs with independence number 2.

Original language	English (US)
Pages (from-to)	3985-3991
Number of pages	7
Journal	Discrete Mathematics
Volume	309
Issue number	12
DOIs	https://doi.org/10.1016/j.disc.2008.11.016
State	Published - Jun 28 2009

Keywords

Double-critical graphs
Graph coloring
Independence number
Quasi-line graphs

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/j.disc.2008.11.016

Library availability

Discover UIUC Full Text

Cite this

@article{37c038bbcd3e432b810a9daa29db002a,

title = "The Erdo{double acute}s-Lov{\'a}sz Tihany conjecture for quasi-line graphs",

abstract = "Erdo{double acute}s and Lov{\'a}sz conjectured in 1968 that for every graph G with χ (G) > ω (G) and any two integers s, t ≥ 2 with s + t = χ (G) + 1, there is a partition (S, T) of the vertex set V (G) such that χ (G [S]) ≥ s and χ (G [T]) ≥ t. Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for quasi-line graphs and for graphs with independence number 2.",

keywords = "Double-critical graphs, Graph coloring, Independence number, Quasi-line graphs",

author = "J{\'o}zsef Balogh and Kostochka, {Alexandr V.} and Noah Prince and Michael Stiebitz",

note = "Funding Information: The work of the first author was supported by NSF CAREER Grant DMS-0745185 and DMS-0600303, UIUC Campus Research Board Grants 06139 and 07048, and OTKA grant 049398. Funding Information: The work of the second author was supported by NSF Grant DMS-06-50784 and grant 06-01-00694 of the Russian Foundation for Basic Research.",

year = "2009",

month = jun,

day = "28",

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

language = "English (US)",

volume = "309",

pages = "3985--3991",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "12",

}

TY - JOUR

T1 - The Erdo{double acute}s-Lovász Tihany conjecture for quasi-line graphs

AU - Balogh, József

AU - Kostochka, Alexandr V.

AU - Prince, Noah

AU - Stiebitz, Michael

N1 - Funding Information: The work of the first author was supported by NSF CAREER Grant DMS-0745185 and DMS-0600303, UIUC Campus Research Board Grants 06139 and 07048, and OTKA grant 049398. Funding Information: The work of the second author was supported by NSF Grant DMS-06-50784 and grant 06-01-00694 of the Russian Foundation for Basic Research.

PY - 2009/6/28

Y1 - 2009/6/28

N2 - Erdo{double acute}s and Lovász conjectured in 1968 that for every graph G with χ (G) > ω (G) and any two integers s, t ≥ 2 with s + t = χ (G) + 1, there is a partition (S, T) of the vertex set V (G) such that χ (G [S]) ≥ s and χ (G [T]) ≥ t. Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for quasi-line graphs and for graphs with independence number 2.

AB - Erdo{double acute}s and Lovász conjectured in 1968 that for every graph G with χ (G) > ω (G) and any two integers s, t ≥ 2 with s + t = χ (G) + 1, there is a partition (S, T) of the vertex set V (G) such that χ (G [S]) ≥ s and χ (G [T]) ≥ t. Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for quasi-line graphs and for graphs with independence number 2.

KW - Double-critical graphs

KW - Graph coloring

KW - Independence number

KW - Quasi-line graphs

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

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

U2 - 10.1016/j.disc.2008.11.016

DO - 10.1016/j.disc.2008.11.016

M3 - Article

AN - SCOPUS:67349162930

SN - 0012-365X

VL - 309

SP - 3985

EP - 3991

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 12

ER -

The Erdo{double acute}s-Lovász Tihany conjecture for quasi-line graphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this