Diameter of 4-colourable graphs

É Czabarka; P. Dankelmann; L. A. Székely

doi:10.1016/j.ejc.2008.09.005

Diameter of 4-colourable graphs

É Czabarka, P. Dankelmann, L. A. Székely

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

9 Citations (Scopus)

Abstract

We prove that for every connected 4-colourable graph G of order n and minimum degree δ ≥ 1, diam (G) ≤ frac(5 n, 2 δ) - 1. This is a first step toward proving a conjecture of Erdo{double acute}s, Pach, Pollack and Tuza [P. Erdo{double acute}s, J. Pach, R. Pollack, Z. Tuza, Radius, diameter, and minimum degree, J. Combin. Theory B 47 (1989) 279-285] from 1989. Our bound is tight since a family of graphs constructed in the above-cited reference has diameter frac(5 n, 2 δ) - 5.

Original language	English
Pages (from-to)	1082-1089
Number of pages	8
Journal	European Journal of Combinatorics
Volume	30
Issue number	5
DOIs	https://doi.org/10.1016/j.ejc.2008.09.005
Publication status	Published - Jul 2009
Externally published	Yes

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2008.09.005

Cite this

@article{0fceaf4867e64f85a9931434e6ce9ac6,

title = "Diameter of 4-colourable graphs",

abstract = "We prove that for every connected 4-colourable graph G of order n and minimum degree δ ≥ 1, diam (G) ≤ frac(5 n, 2 δ) - 1. This is a first step toward proving a conjecture of Erdo\{double acute\}s, Pach, Pollack and Tuza [P. Erdo\{double acute\}s, J. Pach, R. Pollack, Z. Tuza, Radius, diameter, and minimum degree, J. Combin. Theory B 47 (1989) 279-285] from 1989. Our bound is tight since a family of graphs constructed in the above-cited reference has diameter frac(5 n, 2 δ) - 5.",

author = "{\'E} Czabarka and P. Dankelmann and Sz{\'e}kely, \{L. A.\}",

year = "2009",

month = jul,

doi = "10.1016/j.ejc.2008.09.005",

language = "English",

volume = "30",

pages = "1082--1089",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

number = "5",

}

TY - JOUR

T1 - Diameter of 4-colourable graphs

AU - Czabarka, É

AU - Dankelmann, P.

AU - Székely, L. A.

PY - 2009/7

Y1 - 2009/7

N2 - We prove that for every connected 4-colourable graph G of order n and minimum degree δ ≥ 1, diam (G) ≤ frac(5 n, 2 δ) - 1. This is a first step toward proving a conjecture of Erdo{double acute}s, Pach, Pollack and Tuza [P. Erdo{double acute}s, J. Pach, R. Pollack, Z. Tuza, Radius, diameter, and minimum degree, J. Combin. Theory B 47 (1989) 279-285] from 1989. Our bound is tight since a family of graphs constructed in the above-cited reference has diameter frac(5 n, 2 δ) - 5.

AB - We prove that for every connected 4-colourable graph G of order n and minimum degree δ ≥ 1, diam (G) ≤ frac(5 n, 2 δ) - 1. This is a first step toward proving a conjecture of Erdo{double acute}s, Pach, Pollack and Tuza [P. Erdo{double acute}s, J. Pach, R. Pollack, Z. Tuza, Radius, diameter, and minimum degree, J. Combin. Theory B 47 (1989) 279-285] from 1989. Our bound is tight since a family of graphs constructed in the above-cited reference has diameter frac(5 n, 2 δ) - 5.

UR - https://www.scopus.com/pages/publications/63149161256

U2 - 10.1016/j.ejc.2008.09.005

DO - 10.1016/j.ejc.2008.09.005

M3 - Article

AN - SCOPUS:63149161256

SN - 0195-6698

VL - 30

SP - 1082

EP - 1089

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 5

ER -

Diameter of 4-colourable graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this