On kernel-perfect orientations of line graphs

O. V. Borodin; A. V. Kostochka; D. R. Woodall

doi:10.1016/S0012-365X(98)00091-0

On kernel-perfect orientations of line graphs

O. V. Borodin, A. V. Kostochka, D. R. Woodall

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

Abstract

We exploit the technique of Galvin (1995) to prove that an orientation D of a line-graph G (of a multigraph) is kernel-perfect if and only if every oriented odd cycle in D has a chord (or pseudochord) and every clique has a kernel.

Original language	English (US)
Pages (from-to)	45-49
Number of pages	5
Journal	Discrete Mathematics
Volume	191
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(98)00091-0
State	Published - Sep 28 1998
Externally published	Yes

Keywords

Kernel-perfect digraphs
Line graphs
Orientations

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/S0012-365X(98)00091-0

Library availability

Discover UIUC Full Text

Cite this

@article{a2029009ffad4a899e0f1d968d3f2fe6,

title = "On kernel-perfect orientations of line graphs",

abstract = "We exploit the technique of Galvin (1995) to prove that an orientation D of a line-graph G (of a multigraph) is kernel-perfect if and only if every oriented odd cycle in D has a chord (or pseudochord) and every clique has a kernel.",

keywords = "Kernel-perfect digraphs, Line graphs, Orientations",

author = "Borodin, {O. V.} and Kostochka, {A. V.} and Woodall, {D. R.}",

note = "Funding Information: * Corresponding author. E-mail: [email protected]. I This work was partially supported by the grant 96-01-01614 of the Russian Foundation for Fundamental Research. 2 This work was partially supported by the grant 96-01-01614 of the Russian Foundation for Fundamental Research and by the Network DIMANET of the European Union.",

year = "1998",

month = sep,

day = "28",

doi = "10.1016/S0012-365X(98)00091-0",

language = "English (US)",

volume = "191",

pages = "45--49",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - On kernel-perfect orientations of line graphs

AU - Borodin, O. V.

AU - Kostochka, A. V.

AU - Woodall, D. R.

N1 - Funding Information: * Corresponding author. E-mail: [email protected]. I This work was partially supported by the grant 96-01-01614 of the Russian Foundation for Fundamental Research. 2 This work was partially supported by the grant 96-01-01614 of the Russian Foundation for Fundamental Research and by the Network DIMANET of the European Union.

PY - 1998/9/28

Y1 - 1998/9/28

N2 - We exploit the technique of Galvin (1995) to prove that an orientation D of a line-graph G (of a multigraph) is kernel-perfect if and only if every oriented odd cycle in D has a chord (or pseudochord) and every clique has a kernel.

AB - We exploit the technique of Galvin (1995) to prove that an orientation D of a line-graph G (of a multigraph) is kernel-perfect if and only if every oriented odd cycle in D has a chord (or pseudochord) and every clique has a kernel.

KW - Kernel-perfect digraphs

KW - Line graphs

KW - Orientations

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

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

U2 - 10.1016/S0012-365X(98)00091-0

DO - 10.1016/S0012-365X(98)00091-0

M3 - Article

AN - SCOPUS:0042597398

SN - 0012-365X

VL - 191

SP - 45

EP - 49

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

On kernel-perfect orientations of line graphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this