A nowhere-zero k-flow on a graph G=(V(G),E(G))is a pair(D,f),where D is an orientation on E(G)and f:E(G)→{±1,±2,,±(k-1)}is a function such that the total outflow equals to the total inflow at each vert...A nowhere-zero k-flow on a graph G=(V(G),E(G))is a pair(D,f),where D is an orientation on E(G)and f:E(G)→{±1,±2,,±(k-1)}is a function such that the total outflow equals to the total inflow at each vertex.This concept was introduced by Tutte as an extension of face colorings,and Tutte in 1954 conjectured that every bridgeless graph admits a nowhere-zero 5-flow,known as the 5-Flow Conjecture.This conjecture is verified for some graph classes and remains unresolved as of today.In this paper,we show that every bridgeless graph of Euler genus at most 20 admits a nowhere-zero 5-flow,which improves several known results.展开更多
A proper conflict-free k-coloring of a graph is a proper k-coloring in which each nonisolated vertex has a color that appears ex-actly once in its open neighborhood.A graph is PCF k-colorable if it admits a proper con...A proper conflict-free k-coloring of a graph is a proper k-coloring in which each nonisolated vertex has a color that appears ex-actly once in its open neighborhood.A graph is PCF k-colorable if it admits a proper conflict-free k-coloring.The PCF chromatic number of a graph G,denoted by χ_(pcf)(G),is the minimum k such that G is PCF k-colorable.Caro et al conjectured that for a connected graph G with maximum degreeΔ≥3,χ_(pcf)(G)≤Δ+1.One case in this conjecture,a connected graph with maximum degree 3 is PCF 4-colorable,can be derived from the result of Liu and Yu.Jiménez et al stated that the upper bound of PCF chromatic number of a graph G is max{5,x(G)}without a proof.In this paper,we give new proofs of the two results above and derive that for a connected graph G with maximum degreeΔ≥3,its complete subdivision is PCF(Δ+1)-colorable.展开更多
文摘A nowhere-zero k-flow on a graph G=(V(G),E(G))is a pair(D,f),where D is an orientation on E(G)and f:E(G)→{±1,±2,,±(k-1)}is a function such that the total outflow equals to the total inflow at each vertex.This concept was introduced by Tutte as an extension of face colorings,and Tutte in 1954 conjectured that every bridgeless graph admits a nowhere-zero 5-flow,known as the 5-Flow Conjecture.This conjecture is verified for some graph classes and remains unresolved as of today.In this paper,we show that every bridgeless graph of Euler genus at most 20 admits a nowhere-zero 5-flow,which improves several known results.
基金Supported by the Youth Fund of Lanzhou Jiaotong University(1200061328)。
文摘A proper conflict-free k-coloring of a graph is a proper k-coloring in which each nonisolated vertex has a color that appears ex-actly once in its open neighborhood.A graph is PCF k-colorable if it admits a proper conflict-free k-coloring.The PCF chromatic number of a graph G,denoted by χ_(pcf)(G),is the minimum k such that G is PCF k-colorable.Caro et al conjectured that for a connected graph G with maximum degreeΔ≥3,χ_(pcf)(G)≤Δ+1.One case in this conjecture,a connected graph with maximum degree 3 is PCF 4-colorable,can be derived from the result of Liu and Yu.Jiménez et al stated that the upper bound of PCF chromatic number of a graph G is max{5,x(G)}without a proof.In this paper,we give new proofs of the two results above and derive that for a connected graph G with maximum degreeΔ≥3,its complete subdivision is PCF(Δ+1)-colorable.
