Premium
A relaxation of the strong Bordeaux Conjecture
Author(s) -
Huang Ziwen,
Li Xiangwen,
Yu Gexin
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22208
Subject(s) - combinatorics , mathematics , conjecture , vertex (graph theory) , graph , induced subgraph , discrete mathematics
Abstract Letc 1 , c 2 , … , c kbe k nonnegative integers. A graph G is ( c 1 , c 2 , … , c k ) ‐colorable if the vertex set can be partitioned into k setsV 1 , V 2 , … , V k , such that the subgraph G [ V i ] , induced by V i , has maximum degree at most c i for i = 1 , 2 , … , k . Let F denote the family of plane graphs with neither adjacent 3‐cycles nor 5‐cycles. Borodin and Raspaud (2003) conjectured that each graph in F is (0, 0, 0)‐colorable (which was disproved very recently). In this article, we prove that each graph in F is (1, 1, 0)‐colorable, which improves the results by Xu (2009) and Liu‐Li‐Yu (2016).