The adjacent vertex distinguishing total chromatic numbers of planar graphs with Δ=10

The adjacent vertex distinguishing total chromatic numbers of planar graphs with Δ=10

0.00 Avg rating0 Votes
Article ID: iaor20172795
Volume: 34
Issue: 2
Start Page Number: 383
End Page Number: 397
Publication Date: Aug 2017
Journal: Journal of Combinatorial Optimization
Authors: , ,
Keywords: combinatorial optimization, graphs, heuristics
Abstract:

A (proper) total‐k‐coloring of a graph G is a mapping ϕ : V ( G ) E ( G ) { 1 , 2 , , k } equ1 such that any two adjacent elements in V ( G ) E ( G ) equ2 receive different colors. Let C(v) denote the set of the color of a vertex v and the colors of all incident edges of v. A total‐k‐adjacent vertex distinguishing‐coloring of G is a total‐k‐coloring of G such that for each edge u v E ( G ) equ3 , C ( u ) C ( v ) equ4 . We denote the smallest value k in such a coloring of G by χ a ( G ) equ5 . It is known that χ a ( G ) Δ ( G ) + 3 equ6 for any planar graph with Δ ( G ) 11 equ7 . In this paper, we show that if G is a planar graph with Δ ( G ) 10 equ8 , then χ a ( G ) Δ ( G ) + 3 equ9 . Our approach is based on Combinatorial Nullstellensatz and the discharging method.

Reviews

Required fields are marked *. Your email address will not be published.