Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8941797 | Discrete Applied Mathematics | 2018 | 9 Pages |
Abstract
A mod (2p+1)-orientation D is an orientation of G such that dD+(v)â¡dDâ(v)(mod2p+1) for any vertex vâV(G). Extending Tutte's integer flow conjectures, it was conjectured by Jaeger that every 4p-edge-connected graph has a mod (2p+1)-orientation. However, this conjecture has been disproved in Han et al. (2018) recently. Infinite families of 4p-edge-connected graphs (for pâ¥3) and (4p+1)-edge-connected graphs (for pâ¥5) with no mod (2p+1)-orientation are constructed in Han et al. (2018). In this paper, we show that every family of graphs with bounded independence number has only finitely many contraction obstacles for admitting mod (2p+1)-orientations, contrasting to those infinite families. More precisely, we prove that for any integer tâ¥2, there exists a finite family F=F(p,t) of graphs that do not have a mod (2p+1)-orientation, such that every graph G with independence number at most t either admits a mod (2p+1)-orientation or is contractible to a member in F. This indicates that the problem of determining whether every k-edge-connected graph with independence number at most t admits a mod (2p+1)-orientation is computationally solvable for fixed k and t. In particular, the graph family F(p,2) is determined, and our results imply that every 8-edge-connected graph G with independence number at most two admits a mod 5-orientation.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Miaomiao Han, Hong-Jian Lai, Jiaao Li,