A Characterization of Graphs with Fractional Total Chromatic Number Equal to Δ + 2

Takehiro Ito; W. Sean Kennedy; Bruce A. Reed

doi:10.1016/j.endm.2009.11.039

A Characterization of Graphs with Fractional Total Chromatic Number Equal to Δ + 2

Takehiro Ito, W. Sean Kennedy, Bruce A. Reed

INF - System Information Sciences

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

4 Citations (Scopus)

Abstract

For a simple graph of maximum degree Δ, the complexity of computing the fractional total chromatic number is unknown. Trivially it is at least Δ + 1. Kilakos and Reed proved that it is at most Δ + 2. In this paper, we strengthen this by characterizing exactly those simple graphs with fractional total chromatic number Δ + 2. This yields a simple linear-time algorithm to determine whether a given graph has fractional chromatic number Δ + 2. Crown

Original language	English
Pages (from-to)	235-240
Number of pages	6
Journal	Electronic Notes in Discrete Mathematics
Volume	35
Issue number	C
DOIs	https://doi.org/10.1016/j.endm.2009.11.039
Publication status	Published - 2009 Dec 1

Keywords

edge colouring
fractional total colouring
graph theory

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2009.11.039

Cite this

@article{962130d50a12476badbf9445ec8e6c15,

title = "A Characterization of Graphs with Fractional Total Chromatic Number Equal to Δ + 2",

abstract = "For a simple graph of maximum degree Δ, the complexity of computing the fractional total chromatic number is unknown. Trivially it is at least Δ + 1. Kilakos and Reed proved that it is at most Δ + 2. In this paper, we strengthen this by characterizing exactly those simple graphs with fractional total chromatic number Δ + 2. This yields a simple linear-time algorithm to determine whether a given graph has fractional chromatic number Δ + 2. Crown",

keywords = "edge colouring, fractional total colouring, graph theory",

author = "Takehiro Ito and Kennedy, {W. Sean} and Reed, {Bruce A.}",

year = "2009",

month = dec,

day = "1",

doi = "10.1016/j.endm.2009.11.039",

language = "English",

volume = "35",

pages = "235--240",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

number = "C",

}

TY - JOUR

T1 - A Characterization of Graphs with Fractional Total Chromatic Number Equal to Δ + 2

AU - Ito, Takehiro

AU - Kennedy, W. Sean

AU - Reed, Bruce A.

PY - 2009/12/1

Y1 - 2009/12/1

N2 - For a simple graph of maximum degree Δ, the complexity of computing the fractional total chromatic number is unknown. Trivially it is at least Δ + 1. Kilakos and Reed proved that it is at most Δ + 2. In this paper, we strengthen this by characterizing exactly those simple graphs with fractional total chromatic number Δ + 2. This yields a simple linear-time algorithm to determine whether a given graph has fractional chromatic number Δ + 2. Crown

AB - For a simple graph of maximum degree Δ, the complexity of computing the fractional total chromatic number is unknown. Trivially it is at least Δ + 1. Kilakos and Reed proved that it is at most Δ + 2. In this paper, we strengthen this by characterizing exactly those simple graphs with fractional total chromatic number Δ + 2. This yields a simple linear-time algorithm to determine whether a given graph has fractional chromatic number Δ + 2. Crown

KW - edge colouring

KW - fractional total colouring

KW - graph theory

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

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

U2 - 10.1016/j.endm.2009.11.039

DO - 10.1016/j.endm.2009.11.039

M3 - Article

AN - SCOPUS:70949083271

SN - 1571-0653

VL - 35

SP - 235

EP - 240

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

IS - C

ER -

A Characterization of Graphs with Fractional Total Chromatic Number Equal to Δ + 2

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this