Incidence coloring of k-degenerated graphs

We prove that the incidence coloring number of every k-degenerated graph G is at most Δ( G)+2 k−1. For K 4-minor free graphs ( k=2), we decrease this bound to Δ( G)+2, which is tight. For planar graphs ( k=5), we decrease this bound to Δ( G)+7.

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2004-06, Vol.283 (1), p.121-128
Main Authors: Hosseini Dolama, Mohammad, Sopena, Éric, Zhu, Xuding
Format: Article
Language:English
Subjects:
Combinatorics
Combinatorics. Ordered structures
Computer Science
Discrete Mathematics
Exact sciences and technology
Graph theory
Incidence coloring
k-degenerated graph
K4-minor free graph
Mathematics
Other
Planar graph
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We prove that the incidence coloring number of every k-degenerated graph G is at most Δ( G)+2 k−1. For K 4-minor free graphs ( k=2), we decrease this bound to Δ( G)+2, which is tight. For planar graphs ( k=5), we decrease this bound to Δ( G)+7.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2004.01.015