期刊
SIAM JOURNAL ON DISCRETE MATHEMATICS
卷 34, 期 3, 页码 1725-1768出版社
SIAM PUBLICATIONS
DOI: 10.1137/19M1299712
关键词
near-bipartite; potential method; 4-critical; coloring
资金
- NSA [H98230-15-1-0013]
A multigraph G is near-bipartite if V(G) can be partitioned as I, F such that I is an independent set and F induces a forest. We prove that a multigraph G is near-bipartite when 3 vertical bar W vertical bar - 2 vertical bar E(G[W])vertical bar >= -1 for every W subset of V(G), and G contains no K-4 and no Moser spindle. We prove that a simple graph G is near-bipartite when 8 vertical bar W vertical bar - 5 vertical bar E(G[W])vertical bar >= -4 for every W subset of V(G), and G contains no subgraph from some finite family H. We also construct infinite families to show that both results are the best possible in a very sharp sense.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据