×

Modulo orientations with bounded independence number. (English) Zbl 1394.05040

Summary: A \(\operatorname{mod}\,(2 p + 1)\)-orientation \(D\) is an orientation of \(G\) such that \(d_D^+(v) \equiv d_D^-(v)\pmod{2 p + 1}\) for any vertex \(v \in V(G)\). Extending Tutte’s integer flow conjectures [W. T. Tutte, Can. J. Math. 6, 80–91 (1954; Zbl 0055.17101)], it was conjectured by Jaeger that every \(4 p\)-edge-connected graph has a \(\operatorname{mod}\, (2 p + 1)\)-orientation. However, this conjecture has been disproved in [M. Han et al., J. Comb. Theory, Ser. B 131, 1–11 (2018; Zbl 1387.05107)] recently. Infinite families of \(4 p\)-edge-connected graphs (for \(p \geq 3\)) and \((4 p + 1)\)-edge-connected graphs (for \(p \geq 5\)) with no \(\operatorname{mod}\, (2 p + 1)\)-orientation are constructed in M. Han et al. [loc. cit.]. In this paper, we show that every family of graphs with bounded independence number has only finitely many contraction obstacles for admitting \(\operatorname{mod}\, (2 p + 1)\)-orientations, contrasting to those infinite families. More precisely, we prove that for any integer \(t \geq 2\), there exists a finite family \(\mathcal{F} = \mathcal{F}(p, t)\) of graphs that do not have a \(\operatorname{mod}\, (2 p + 1)\)-orientation, such that every graph \(G\) with independence number at most \(t\) either admits a \(\operatorname{mod}\, (2 p + 1)\)-orientation or is contractible to a member in \(\mathcal{F}\). This indicates that the problem of determining whether every \(k\)-edge-connected graph with independence number at most \(t\) admits a \(\operatorname{mod}\, (2 p + 1)\)-orientation is computationally solvable for fixed \(k\) and \(t\). In particular, the graph family \(\mathcal{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.

MSC:

05C21 Flows in graphs
05C40 Connectivity
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: DOI

References:

[1] Bondy, J. A.; Murty, U. S.R., Graph theory with applications, (1976), American Elsevier · Zbl 1226.05083
[2] Hakimi, S. L., On the degrees of the vertices of a directed graph, J. Franklin Inst., 279, 290-308, (1965) · Zbl 0173.26404
[3] Han, M.; Li, J.; Wu, Y.; Zhang, C.-Q., Counterexamples to jaeger’s circular flow conjecture, J. Combin. Theory Ser. B, (2018) · Zbl 1387.05107
[4] Jaeger, F., On circular flows in graphs, (Finite and Infinite Sets, (Eger, 1981), Colloq. Math. Soc. Janos Bolyai, vol. 37, (1984), North-Holland Amsterdam), 391-402 · Zbl 0567.05049
[5] Jaeger, F., Nowhere-zero flow problems, (Beineke, L.; Wilson, R., Selected Topics in Graph Theory, Vol. 3, (1988), Academic Press London, New York), 91-95 · Zbl 0658.05034
[6] Jaeger, F.; Linial, N.; Payan, C.; Tarsi, M., Group connectivity of graphs-a nonhomogeneous analogue of nowhere-zero flow properties, J. Combin. Theory Ser. B, 56, 165-182, (1992) · Zbl 0824.05043
[7] Kochol, M., An equivalent version of the 3-flow conjecture, J. Combin. Theory Ser. B, 83, 258-261, (2001) · Zbl 1029.05088
[8] Lai, H.-J., Mod \((2 p + 1)\)-orientations and \(K_{1, 2 p + 1}\)-decompositions, SIAM J. Discrete Math., 21, 844-850, (2007) · Zbl 1151.05040
[9] Lai, H.-J.; Liang, Y.; Liu, J.; Miao, Z.; Meng, J.; Shao, Y.; Zhang, Z., On strongly \(\mathbb{Z}_{2 s + 1}\)-connected graphs, Discrete Appl. Math., 174, 73-80, (2014) · Zbl 1297.05132
[10] Lai, H.-J.; Luo, R.; Zhang, C.-Q., Integer flow and orientation, (Beineke, L.; Wilson, R., Topics in Chromatic Graph Theory, Encyclopedia of Mathematics and Its Applications, vol. 156, (2015)), 181-198 · Zbl 1317.05004
[11] Li, J.; Luo, R.; Wang, Yi, Nowhere-zero 3-flow with small independence number, Discrete Math., 341, 42-50, (2018) · Zbl 1372.05095
[12] Liang, Y.; Cycles, Disjoint spanning trees, and orientation of graphs, (2012), West Virginia University Morgantown, WV, (Ph.D. dissertation)
[13] Liang, Y.; Lai, H.-J.; Luo, R.; Xu, R., Extendability of contractible configurations for nowhere-zero flows and modulo orientations, Graphs Combin., 32, 1065-1075, (2016) · Zbl 1339.05166
[14] Lovász, L. M.; Thomassen, C.; Wu, Y.; Zhang, C.-Q., Nowhere-zero 3-flows and modulo \(k\)-orientations, J. Combin. Theory Ser. B, 103, 587-598, (2013) · Zbl 1301.05154
[15] Luo, R.; Miao, Z.; Xu, R., Nowhere-zero 3-flows of graphs with independence number two, Graphs Combin., 29, 1899-1907, (2013) · Zbl 1282.05057
[16] Thomassen, C., The weak 3-flow conjecture and the weak circular flow conjecture, J. Combin. Theory Ser. B, 102, 521-529, (2012) · Zbl 1239.05083
[17] Tutte, W. T., On the imbedding of linear graphs in surfaces, Proc. Lond. Math. Soc. Ser. 2, 51, 474-483, (1949) · Zbl 0033.30803
[18] Tutte, W. T., A contribution to the theory of chromatical polynomials, Canad. J. Math., 6, 80-91, (1954) · Zbl 0055.17101
[19] Wu, Y., Integer flows and modulo orientations, (2012), West Virginia University Morgantown, WV, (Ph.D. dissertation)
[20] Younger, D. H., Integer flows, J. Graph Theory, 7, 349-357, (1983) · Zbl 0515.05057
[21] Zhang, C.-Q., Integer flows and cycle covers of graphs, (1997), Marcel Dekker Inc. New York
[22] Zhang, C.-Q., Circular flows of nearly Eulerian graphs and vertex-splitting, J. Graph Theory, 40, 147-161, (2002) · Zbl 1004.05039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.