We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A (2, 1)-Decomposition of Planar Graphs Without Intersecting 3-Cycles and Adjacent 4--Cycles.
- Authors
Tian, Fangyu; Li, Xiangwen
- Abstract
Let G be a graph. For two positive integers d and h, a (d, h)-decomposition of G is a pair (G, H) such that H is a subgraph of G of maximum degree at most h and D is an acyclic orientation of G - E (H) of maximum out-degree at most d. A graph G is (d, h)-decomposable if G has a (d, h)-decomposition. In this paper, we prove that every planar graph without intersecting 3-cycles and adjacent 4 - -cycles is (2, 1)-decomposable. As a corollary, we obtain that every planar graph without intersecting 3-cycles and adjacent 4 - -cycles has a matching M such that G - M is 2-degenerate and hence G - M is DP-3-colorable and Alon-Tarsi number of G - M is at most 3.
- Subjects
PLANAR graphs; INTEGERS
- Publication
Graphs & Combinatorics, 2023, Vol 39, Issue 6, p1
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-023-02708-x