On the 4-flow nullity of graphs. (English) Zbl 1519.05100
Summary: The \(k\)-flow nullity \(n_k (G)\) of a graph \(G\) is the minimum number \(n\) for which \(G\) admits a \(k\)-flow \((D,\psi)\) such that there are exactly \(n\) edges \(e\) with \(\psi (e)=0\). Let \(X\) and \(Y\) be two subgraphs of \(G\). It is proved that \(n_4 (X\cup Y)\leq n_4 (X)+n_4 (Y)\) if \(|E(X)\cap E(Y)|=4\) and the subgraph of \(G\) induced by \(E(X)\cap E(Y)\) is a connected graph which is not a tree with 2 or 3 leaves.
References:
| [1] | Bondy, JA; Murty, USR, Graph Theory with Applications (1976), London: Macmillan, London · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2 |
| [2] | Catlin, PA, Double cycle covers and the Petersen graph, J. Graph Theory, 13, 465-483 (1989) · Zbl 0713.05040 · doi:10.1002/jgt.3190130408 |
| [3] | Celmins, U.A.: On cubic graphs that do not have an edge 3-colouring. Ph.D. thesis, University of Waterloo (1985) |
| [4] | Deng, F., Zhang, J.: A note on nowhere-zero 4-flows of graphs. Preprint (2023) |
| [5] | Jaeger, F., Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B, 26, 205-216 (1979) · Zbl 0422.05028 · doi:10.1016/0095-8956(79)90057-1 |
| [6] | Lovász, LM; 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 · doi:10.1016/j.jctb.2013.06.003 |
| [7] | Seymour, PD, Nowhere-zero 6-flows, J. Combin. Theory Ser. B, 30, 130-135 (1981) · Zbl 0474.05028 · doi:10.1016/0095-8956(81)90058-7 |
| [8] | 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 · doi:10.1016/j.jctb.2011.09.003 |
| [9] | Tutte, WT, On the imbedding of linear graphs in surfaces, Proc. Lond. Math. Soc., s2-51, 474-483 (1949) · Zbl 0033.30803 · doi:10.1112/plms/s2-51.6.474 |
| [10] | Tutte, WT, A contribution to the theory of chromatic polynomials, J. Can. Math. Soc., 6, 80-91 (1954) · Zbl 0055.17101 · doi:10.4153/CJM-1954-010-9 |
| [11] | Zhang, C-Q, Integer Flows and Cycle Covers of Graphs (1997), New York: Marcel Dekker Inc, New York |
| [12] | Zhang, J-Y; Lu, N., Flow modules and nowhere-zero flows, J. Algebr. Comb., 57, 481-493 (2023) · Zbl 1512.05166 · doi:10.1007/s10801-022-01177-4 |
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.
