Dynamic coloring of graphs having no K5 minor

被引：8

作者：

Kim, Younjin ^{[1
]}

Lee, Sang June ^{[2
]}

Oum, Sang-il ^{[3
,4
]}

机构：

[1] Ewha Womans Univ, Dept Math, Seoul, South Korea

[2] Duksung Womens Univ, Dept Math, Seoul, South Korea

[3] Korea Adv Inst Sci & Technol, Dept Math Sci, Daejeon, South Korea

[4] KIAS, Sch Math, Seoul, South Korea

来源：

DISCRETE APPLIED MATHEMATICS | 2016年 / 206卷

基金：

新加坡国家研究基金会;

关键词：

Dynamic coloring; Minor-free graph; Four color theorem; Hadwiger's conjecture; LOCAL CHROMATIC NUMBER; CONJECTURE;

D O I：

10.1016/j.dam.2016.01.022

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We prove that every simple connected graph with no K5 minor admits a proper 4-coloring such that the neighborhood of each vertex v having more than one neighbor is not monochromatic, unless the graph is isomorphic to the cycle of length 5. This generalizes the result on planar graphs by 5.-J. Kim, W.J. Park and the second author [Discrete Appl. Math. 161 (2013) 2207-22121. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：81 / 89

页数：9

共 28 条

[21] Extremal spectral radius of K3,3/K2,4-minor free graphs
Wang, Bing
Chen, Wenwen
Fang, Longfei
LINEAR ALGEBRA AND ITS APPLICATIONS, 2021, 628 : 103 - 114
[22] Spectral extremal results on the Aα-spectral radius of graphs without K a,b-minor
Lei, Xingyu
Li, Shuchao
APPLIED MATHEMATICS AND COMPUTATION, 2025, 492
[23] Maxima of the Q-index: Graphs with no K1,t-minor
Zhang, Yanting
Lou, Zhenzhen
LINEAR ALGEBRA AND ITS APPLICATIONS, 2022, 653 : 135 - 150
[24] Neighbor sum distinguishing total colorings of K4-minor free graphs
Hualong Li
Bingqiang Liu
Guanghui Wang
Frontiers of Mathematics in China, 2013, 8 : 1351 - 1366
[25] Approximation Algorithm and FPT Algorithm for Connected-k-Subgraph Cover on Minor-Free Graphs
Liu, Pengcheng
Zhang, Zhao
Ran, Yingli
Huang, Xiaohui
MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE, 2024, 34 (03) : 180 - 192
[26] Spectral Turán problem for K-5-free signed graphs
Wang, Yongang
LINEAR ALGEBRA AND ITS APPLICATIONS, 2024, 691 : 96 - 108
[27] The r-dynamic chromatic number of planar graphs without 4-,5-cycles
Ruiying Yang
Yuehua Bu
Junlei Zhu
Hongguo Zhu
Journal of Combinatorial Optimization, 2023, 45
[28] Injective Chromatic Index of K4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_4$$\end{document}-Minor Free Graphs
Jian-Bo Lv
Jiacong Fu
Jianxi Li
Graphs and Combinatorics, 2024, 40 (4)

← 1 2 3 →