Name
Title | ||
|---|---|---|
Decomposing a planar graph without triangular 4-cycles into a matching and a 3-colorable graph |
Abstract | ||
|---|---|---|
Let c1,c2,…,ck be non-negative integers. A graph G is (c1,c2,…,ck)-colorable if the vertex set of G can be partitioned into k sets V1,V2,…,Vk, such that G[Vi], the subgraph induced by Vi, has maximum degree at most ci for i∈[k]. In this paper, we prove that every planar graph without triangular 4-cycles is (1,1,1)-colorable. Consequently, such planar graphs can be decomposed into a matching and a 3-colorable graph. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.dam.2019.04.026 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Planar graph,Bad cycles,Superextension,Discharging | Integer,Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Degree (graph theory),Mathematics,Planar graph | Journal |
Volume | ISSN | Citations |
268 | 0166-218X | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ziwen Huang | 1 | 0 | 1.69 |
| Runrun Liu | 2 | 8 | 5.29 |
| Gaozhen Wang | 3 | 0 | 0.34 |