首页|The chromatic number of signed graphs with bounded maximum average degree
The chromatic number of signed graphs with bounded maximum average degree
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
A signed graph is a simple graph with two types of edges: positive and negative edges. Switching a vertex nu of a signed graph corresponds to changing the type of each edge incident to nu. A homomorphism from a signed graph G to another signed graph H is a mapping : phi : V(G) -> V(H) such that, after switching some of the vertices of G, phi maps every edge of G to an edge of H of the same type. The chromatic number chi(s)(G) of a signed graph G is the order of a smallest signed graph H such that there is a homomorphism from G to H. The maximum average degree mad(G) of a graph G is the maximum of the average degrees of all the subgraphs of G. We denote M-k the class of signed graphs with maximum average degree less than k and P-g the class of planar signed graphs of girth at least g. We prove: chi(s)(P7) <= 5, chi(s)(M-17/5) <= 10 which implies chi(s) (P-5) <= 10, chi(s)(M4-8/q+3) <= q + 1 with q a prime power congruent to 1 modulo 4. (C) 2022 Elsevier B.V. All rights reserved.
HomomorphismSigned graphMaximum average degreePlanar graphDischargingHOMOMORPHISMS
NSTL
Elsevier
