<eq200410.gif>-Coloring Problem

Akihiro UEJIMA; Hiro ITO; Tatsuie TSUKIJI

-Coloring Problem

Akihiro UEJIMA, Hiro ITO, Tatsuie TSUKIJI

Full Text Views

0

Share
Cite this

Summary :

H-coloring problem is a coloring problem with restrictions such that some pairs of colors cannot be used for adjacent vertices, where H is a graph representing the restrictions of colors. We deal with the case that H is the complement graph of a cycle of odd order 2p + 1. This paper presents the following results: (1) chordal graphs and internally maximal planar graphs are -colorable if and only if they are p-colorable (p 2), (2) -coloring problem on planar graphs is NP-complete, and (3) there exists a class that includes infinitely many -colorable but non-3-colorable planar graphs.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E87-A No.5 pp.1243-1250

Publication Date: 2004/05/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Graphs and Networks

Cite this

Copy

Akihiro UEJIMA, Hiro ITO, Tatsuie TSUKIJI, "-Coloring Problem" in IEICE TRANSACTIONS on Fundamentals, vol. E87-A, no. 5, pp. 1243-1250, May 2004, doi: .
Abstract: H-coloring problem is a coloring problem with restrictions such that some pairs of colors cannot be used for adjacent vertices, where H is a graph representing the restrictions of colors. We deal with the case that H is the complement graph of a cycle of odd order 2p + 1. This paper presents the following results: (1) chordal graphs and internally maximal planar graphs are -colorable if and only if they are p-colorable (p 2), (2) -coloring problem on planar graphs is NP-complete, and (3) there exists a class that includes infinitely many -colorable but non-3-colorable planar graphs.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e87-a_5_1243/_p

Copy

@ARTICLE{e87-a_5_1243,
author={Akihiro UEJIMA, Hiro ITO, Tatsuie TSUKIJI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={-Coloring Problem},
year={2004},
volume={E87-A},
number={5},
pages={1243-1250},
abstract={H-coloring problem is a coloring problem with restrictions such that some pairs of colors cannot be used for adjacent vertices, where H is a graph representing the restrictions of colors. We deal with the case that H is the complement graph of a cycle of odd order 2p + 1. This paper presents the following results: (1) chordal graphs and internally maximal planar graphs are -colorable if and only if they are p-colorable (p 2), (2) -coloring problem on planar graphs is NP-complete, and (3) there exists a class that includes infinitely many -colorable but non-3-colorable planar graphs.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - -Coloring Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1243
EP - 1250
AU - Akihiro UEJIMA
AU - Hiro ITO
AU - Tatsuie TSUKIJI
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E87-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2004
AB - H-coloring problem is a coloring problem with restrictions such that some pairs of colors cannot be used for adjacent vertices, where H is a graph representing the restrictions of colors. We deal with the case that H is the complement graph of a cycle of odd order 2p + 1. This paper presents the following results: (1) chordal graphs and internally maximal planar graphs are -colorable if and only if they are p-colorable (p 2), (2) -coloring problem on planar graphs is NP-complete, and (3) there exists a class that includes infinitely many -colorable but non-3-colorable planar graphs.
ER -