Partial k-trees with maximum chromatic number

Janka Chlebikova

doi:10.1016/S0012-365X(02)00586-1

Partial k-trees with maximum chromatic number

Janka Chlebikova

School of Computing

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

Abstract

The paper is concerned with partial k-trees whose chromatic number is maximal, i.e. equal to (k+1). We have proved that any such graph contains a triangle (if k>=3), but need not contain a clique on ⌊(k+5)/2⌋ vertices as a subgraph.

Original language	English
Pages (from-to)	269-276
Journal	Discrete Mathematics
Volume	259
Issue number	1-3
Early online date	4 Sept 2002
DOIs	https://doi.org/10.1016/S0012-365X(02)00586-1
Publication status	Published - 2002

Keywords

Partial k-tree
Treewidth
Chromatic number
Clique number

Access to Document

10.1016/S0012-365X(02)00586-1

Cite this

@article{e13e3cb35d72463c80d3c8cae9b0ca07,

title = "Partial k-trees with maximum chromatic number",

abstract = "The paper is concerned with partial k-trees whose chromatic number is maximal, i.e. equal to (k+1). We have proved that any such graph contains a triangle (if k>=3), but need not contain a clique on ⌊(k+5)/2⌋ vertices as a subgraph.",

keywords = "Partial k-tree, Treewidth, Chromatic number, Clique number",

author = "Janka Chlebikova",

year = "2002",

doi = "10.1016/S0012-365X(02)00586-1",

language = "English",

volume = "259",

pages = "269--276",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Partial k-trees with maximum chromatic number

AU - Chlebikova, Janka

PY - 2002

Y1 - 2002

N2 - The paper is concerned with partial k-trees whose chromatic number is maximal, i.e. equal to (k+1). We have proved that any such graph contains a triangle (if k>=3), but need not contain a clique on ⌊(k+5)/2⌋ vertices as a subgraph.

AB - The paper is concerned with partial k-trees whose chromatic number is maximal, i.e. equal to (k+1). We have proved that any such graph contains a triangle (if k>=3), but need not contain a clique on ⌊(k+5)/2⌋ vertices as a subgraph.

KW - Partial k-tree

KW - Treewidth

KW - Chromatic number

KW - Clique number

U2 - 10.1016/S0012-365X(02)00586-1

DO - 10.1016/S0012-365X(02)00586-1

M3 - Article

SN - 0012-365X

VL - 259

SP - 269

EP - 276

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Partial k-trees with maximum chromatic number

Abstract

Keywords

Access to Document

Fingerprint

Cite this