In this paper, we prove that if any set of ｜E（G）｜- ｜V（G）｜ ＋ 1 facial cycles of a 3-connected planar graph G embedded in the plane doesn＇t form a minimum cycle base of G, then any minimum cycle base of G cont...In this paper, we prove that if any set of ｜E（G）｜- ｜V（G）｜ ＋ 1 facial cycles of a 3-connected planar graph G embedded in the plane doesn＇t form a minimum cycle base of G, then any minimum cycle base of G contains a separating cycle, and G has a minor isomorphic to T6, where T6 is the graph obtained from the complete graph K6 by deleting a path with four edges.展开更多
A graph G is k-triangular if each of its edge is contained in at least k triangles. It is conjectured that every 4-edge-connected triangular graph admits a nowhere-zero 3-flow. A triangle-path in a graph G is a sequen...A graph G is k-triangular if each of its edge is contained in at least k triangles. It is conjectured that every 4-edge-connected triangular graph admits a nowhere-zero 3-flow. A triangle-path in a graph G is a sequence of distinct triangles T1T2%…Tk in G such that for 1 〈 i 〈 k - 1, IE（Ti）∩E（Ti＋1）1= 1 and E（Ti） n E（Tj）=φ if j 〉 i＋1. Two edges e, e＇∈ E（G） are triangularly connected if there is a triangle-path T1, T2,... , Tk in G such that e ∈ E（T1） and er ∈ E（Tk）. Two edges e, e＇ ∈E（G） are equivalent if they are the same, parallel or triangularly connected. It is easy to see that this is an equivalent relation. Each equivalent class is called a triangularly connected component. In this paper, we prove that every 4-edge-connected triangular graph G is Z3-connected, unless it has a triangularly connected component which is not Z3-connected but admits a nowhere-zero 3-flow.展开更多
Suppose that G is a planar cubic graph withχi(G)>5.We show that ifχi(H)<χi(G)for each planar cubic graph H of order less thanG,thenG is either a 3-connected simple planar cubic graph,or a planar graph obtaine...Suppose that G is a planar cubic graph withχi(G)>5.We show that ifχi(H)<χi(G)for each planar cubic graph H of order less thanG,thenG is either a 3-connected simple planar cubic graph,or a planar graph obtained from a simple cubic 3-connected planar graph by adding some earrings.This shows that a minimum non-5-injectively colorable simple planar cubic graph must be 3-connected.展开更多
The base graph of a simple matroid M = （E, A） is the graph G such that V（G） = A and E（G） = {BB＇： B, B＇ B, [B ／ B＇｜ = 1}, where the same notation is used for the vertices of G and the bases of M. It is prov...The base graph of a simple matroid M = （E, A） is the graph G such that V（G） = A and E（G） = {BB＇： B, B＇ B, [B ／ B＇｜ = 1}, where the same notation is used for the vertices of G and the bases of M. It is proved that the base graph G of connected simple matroid M is Z3-connected if ｜V（G）｜ ≥5. We also proved that if M is not a connected simple matroid, then the base graph G of M does not admit a nowhere-zero 3-flow if and only if IV（G）[ =4. Furthermore, if for every connected component Ei （ i≥ 2） of M, the matroid base graph Gi of Mi=MIEi has IV（Gi）｜≥5, then G is Z3-connected which also implies that G admits nowhere-zero 3-flow immediately.展开更多
文摘In this paper, we prove that if any set of ｜E（G）｜- ｜V（G）｜ ＋ 1 facial cycles of a 3-connected planar graph G embedded in the plane doesn＇t form a minimum cycle base of G, then any minimum cycle base of G contains a separating cycle, and G has a minor isomorphic to T6, where T6 is the graph obtained from the complete graph K6 by deleting a path with four edges.
文摘A graph G is k-triangular if each of its edge is contained in at least k triangles. It is conjectured that every 4-edge-connected triangular graph admits a nowhere-zero 3-flow. A triangle-path in a graph G is a sequence of distinct triangles T1T2%…Tk in G such that for 1 〈 i 〈 k - 1, IE（Ti）∩E（Ti＋1）1= 1 and E（Ti） n E（Tj）=φ if j 〉 i＋1. Two edges e, e＇∈ E（G） are triangularly connected if there is a triangle-path T1, T2,... , Tk in G such that e ∈ E（T1） and er ∈ E（Tk）. Two edges e, e＇ ∈E（G） are equivalent if they are the same, parallel or triangularly connected. It is easy to see that this is an equivalent relation. Each equivalent class is called a triangularly connected component. In this paper, we prove that every 4-edge-connected triangular graph G is Z3-connected, unless it has a triangularly connected component which is not Z3-connected but admits a nowhere-zero 3-flow.
基金This research was supported by the National Natural Science Foundation of China(Nos.11571180 and 11331003)the Natural Science Foundation of Jiangsu Higher Education Institutions of China(No.17KJB110010).
文摘Suppose that G is a planar cubic graph withχi(G)>5.We show that ifχi(H)<χi(G)for each planar cubic graph H of order less thanG,thenG is either a 3-connected simple planar cubic graph,or a planar graph obtained from a simple cubic 3-connected planar graph by adding some earrings.This shows that a minimum non-5-injectively colorable simple planar cubic graph must be 3-connected.
文摘The base graph of a simple matroid M = （E, A） is the graph G such that V（G） = A and E（G） = {BB＇： B, B＇ B, [B ／ B＇｜ = 1}, where the same notation is used for the vertices of G and the bases of M. It is proved that the base graph G of connected simple matroid M is Z3-connected if ｜V（G）｜ ≥5. We also proved that if M is not a connected simple matroid, then the base graph G of M does not admit a nowhere-zero 3-flow if and only if IV（G）[ =4. Furthermore, if for every connected component Ei （ i≥ 2） of M, the matroid base graph Gi of Mi=MIEi has IV（Gi）｜≥5, then G is Z3-connected which also implies that G admits nowhere-zero 3-flow immediately.
基金NSFC(No.11671186)NSF of Fujian(No.2017J01404)Institute of Meteorological Big Data-Digital Fujian and Fujian Key Laboratory of Data Science and Statistics。
