摘要：
A graph G is
$$(d_{1},d_{2},\ldots ,d_{k})$$
-colorable if the vertex set of G can be partitioned into subsets
$$V_{1}, V_{2},\ldots , V_{k}$$
such that the subgraph
$$G[V_{i}]$$
induced by
$$V_{i}$$
has maximum degree at most
$$d_{i}$$
for
$$i = 1, 2, \ldots , k$$
. Novosibirsk’s Conjecture (Sib lektron Mat Izv 3:428–440, 2006) says that every planar graph without 3-cycles adjacent to cycles of length 3 or 5 is 3-colorable. Borodin et al. (Discrete Math 310: 167–173, 2010) asked whether every planar graph without adjacent cycles of length at most 5 is 3-colorable. Cohen-Addad et al. (J Comb Theory Ser B 122:452–456, 2017) gave a negative answer to both Novosibirsk’s conjecture and Borodin et al.’s problem. Zhang et al. (Discrete Math 339:3032–3042, 2016) asked whether every planar graph without adjacent cycles of length at most 5 is (1,0,0)-colorable. In this paper, we show that every planar graph without adjacent cycles of length at most five is (2,0,0)-colorable, which improves the result of Chen et al. (Discrete Math 339:886–905, 2016) who proved that every planar graph without cycles of length 4 and 5 is (2,0,0)-colorable.
作者机构：
[Yu, Gexin; Li, Xiangwen; Yin, Yuxue] Cent China Normal Univ, Sch Math & Stat, Wuhan 430079, Hubei, Peoples R China.;[Yu, Gexin] Coll William & Mary, Dept Math, Williamsburg, VA 23185 USA.
通讯机构：
[Li, Xiangwen] C;Cent China Normal Univ, Sch Math & Stat, Wuhan 430079, Hubei, Peoples R China.
摘要：
In 1976, Steinberg conjectured that every planar graph without 4-cycles and 5-cycles is 3-colorable, and in 2003, Borodin and Raspaud further conjectured that every planar graph without 5-cycles and K-4(-) is 3-colorable. Both conjectures are disproved in 2016 by Cohen-Addad et al. In this paper, we prove a relaxation of the conjectures that every planar graph without 5-cycles and K-4(-) and adjacent 4-cycles is (2, 0, 0)-colorable, which improves the results of Chen et al. (2016) and of Liu et al. (2015). (C) 2019 Elsevier B.V. All rights reserved.
摘要：
DP-coloring (also known as correspondence coloring) is a generalization of list coloring introduced recently by Dvorak and Postle (2017). Kim and Ozeki proved that planar graphs without k-cycles where k = 3,4,5, or 6 are DP-4-colorable. In this paper, we prove that every planar graph G without k-cycles adjacent to triangles is DP-4-colorable for k = 5,6, which implies that every planar graph G without k-cycles adjacent to triangles is 4-choosable for k = 5,6. This extends the result of Kim and Ozeki on 3-, 5-, and 6-cycles. (C) 2019 Published by Elsevier B.V.
关键词：
Zero-sum flow;5-Regular;Bidirected graph;Cycle-cubic tree
摘要：
Let G be a graph. A zero-sum flow of G is an assignment of nonzero real numbers to the edges of G such that the sum of the values of all edges incident with each vertex is zero. Let k be a natural number. A zero-sum k-flow is a flow with values from the set
$$\{\pm 1, \ldots , \pm (k - 1)\}$$
. In this paper, we prove that every 5-regular graph admits a zero-sum 6-flow.
作者机构：
[Liu, Runrun; Li, Xiangwen] Cent China Normal Univ, Dept Math & Stat, Wuhan 430079, Hubei, Peoples R China.
通讯机构：
[Liu, Runrun] C;Cent China Normal Univ, Dept Math & Stat, Wuhan 430079, Hubei, Peoples R China.
关键词：
DP-coloring;planar graph;discharging
摘要：
Wang and Lih (2002) conjectured that every planar graph without adjacent triangles is 4-choosable. In this paper, we prove that every planar graph without any 4-cycle adjacent to two triangles is DP-4-colorable, which improves the results of Lam et al. (1999), Cheng et al. (2016) and Kim and Yu [arXiv:1709.09809v1]. (C) 2018 Elsevier B.V. All rights reserved.
期刊：
European Journal of Combinatorics,2019年82:102995 ISSN：0195-6698
通讯作者：
Li, Xiangwen
作者机构：
[Liu, Runrun; Li, Xiangwen] Cent China Normal Univ, Sch Math & Stat, Wuhan 430079, Hubei, Peoples R China.
通讯机构：
[Li, Xiangwen] C;Cent China Normal Univ, Sch Math & Stat, Wuhan 430079, Hubei, Peoples R China.
摘要：
DP-coloring as a generalization of list coloring was introduced by Dvorak and Postle in 2017, who proved that every planar graph without cycles from 4 to 8 is 3-choosable, which was conjectured by Borodin et al. in 2007. In this paper, we prove that every planar graph without adjacent cycles of length at most 8 is 3-choosable, which extends this result of Dvorak and Postle. (C) 2019 Elsevier Ltd. All rights reserved.
作者机构：
[Yu, Gexin; Li, Xiangwen; Lv, Jian-Bo] Cent China Normal Univ, Sch Math & Stat, Wuhan 430079, Hubei, Peoples R China.;[Yu, Gexin] Coll William & Mary, Dept Math, Williamsburg, VA 23185 USA.
通讯机构：
[Li, Xiangwen] C;Cent China Normal Univ, Sch Math & Stat, Wuhan 430079, Hubei, Peoples R China.
关键词：
Strong edge-coloring;Strong chromatic index;Maximum average degree;Sparse graphs
摘要：
<jats:title>Abstract</jats:title><jats:p>Let <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22208-math-0001.png" xlink:title="urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0001" /> be <jats:italic>k</jats:italic> nonnegative integers. A graph <jats:italic>G</jats:italic> is <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22208-math-0002.png" xlink:title="urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0002" />‐colorable if the vertex set can be partitioned into <jats:italic>k</jats:italic> sets <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22208-math-0003.png" xlink:title="urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0003" />, such that the subgraph <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22208-math-0004.png" xlink:title="urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0004" />, induced by <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22208-math-0005.png" xlink:title="urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0005" />, has maximum degree at most <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22208-math-0006.png" xlink:title="urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0006" /> for <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22208-math-0007.png" xlink:title="urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0007" />. Let <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22208-math-0008.png" xlink:title="urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0008" /> denote the family of plane graphs with neither adjacent 3‐cycles nor 5‐cycles. Borodin and Raspaud (2003) conjectured that each graph in <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22208-math-0009.png" xlink:title="urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0009" /> is (0, 0, 0)‐colorable (which was disproved very recently). In this article, we prove that each graph in <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22208-math-0010.png" xlink:title="urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0010" /> is (1, 1, 0)‐colorable, which improves the results by Xu (2009) and Liu‐Li‐Yu (2016).</jats:p>
作者机构：
[Hu, Lili; Li, Xiangwen] Cent China Normal Univ, Sch Math & Stat, Wuhan 430079, Hubei, Peoples R China.;[Hu, Lili] Minnan Normal Univ, Zhengzhou 363000, Henan, Peoples R China.
通讯机构：
[Li, Xiangwen] C;Cent China Normal Univ, Sch Math & Stat, Wuhan 430079, Hubei, Peoples R China.
关键词：
Signed graph;Planar graph;3-colorable
摘要：
In this paper, we investigate the signed graph version of Erdös problem: Is there a constant c such that every signed planar graph without k-cycles, where 4≤k≤c, is 3-colorable and prove that each signed planar graph without cycles of length from 4 to 8 is 3-colorable.
摘要：
Jaeger et al. conjectured that every 5-edge-connected graph is $$Z_3$$Z3-connected, which is equivalent to that every 5-edge-connected claw-free graph is $$Z_3$$Z3-connected by Lai et al. (Inf Process Lett 111:1085---1088, 2011), and Ma and Li (Discret Math 336:57---68, 2014). Let G be a claw-free graph on at least 3 vertices such that there are at least two common neighbors of every pair of 2-distant vertices. In this paper, we prove that G is not $$Z_3$$Z3-connected if and only if G is one of seven specified graphs, or three families of well characterized graphs. As a corollary, G does not admit a nowhere-zero 3-flow if and only if G is one of three specified graphs or a family of well characterized graphs. Jaeger et al. conjectured that every 5-edge-connected graph is $$Z_3$$Z3-connected, which is equivalent to that every 5-edge-connected claw-free graph is $$Z_3$$Z3-connected by Lai et al. (Inf Process Lett 111:1085---1088, 2011), and Ma and Li (Discret Math 336:57---68, 2014). Let G be a claw-free graph on at least 3 vertices such that there are at least two common neighbors of every pair of 2-distant vertices. In this paper, we prove that G is not $$Z_3$$Z3-connected if and only if G is one of seven specified graphs, or three families of well characterized graphs. As a corollary, G does not admit a nowhere-zero 3-flow if and only if G is one of three specified graphs or a family of well characterized graphs.
期刊：
Journal of Combinatorial Optimization,2017年33(4):1354-1364 ISSN：1382-6905
通讯作者：
Li, Xiangwen
作者机构：
[Bai, Ying; Yu, Gexin; Li, Xiangwen] Huazhong Normal Univ, Dept Math, Wuhan 430079, Peoples R China.;[Bai, Ying; Yu, Gexin; Li, Xiangwen] Huazhong Normal Univ, Hubei Key Lab Math Sci, Wuhan 430079, Peoples R China.;[Yu, Gexin] Coll William & Mary, Dept Math, Williamsburg, VA 23185 USA.
通讯机构：
[Li, Xiangwen] H;Huazhong Normal Univ, Dept Math, Wuhan 430079, Peoples R China.;Huazhong Normal Univ, Hubei Key Lab Math Sci, Wuhan 430079, Peoples R China.
关键词：
Planar graphs;Improper coloring;Cycle
摘要：
Let
$$c_{1},c_{2},\ldots ,c_{k}$$
be k non-negative integers. A graph G is
$$(c_{1},c_{2},\ldots ,c_{k})$$
-colorable if the vertex set can be partitioned into k sets
$$V_{1},V_{2},\ldots ,V_{k}$$
such that for every
$$i,1\le i\le k$$
, the subgraph
$$G[V_{i}]$$
has maximum degree at most
$$c_{i}$$
. Steinberg (Ann Discret Math 55:211–248, 1993) conjectured that every planar graph without 4- and 5-cycles is 3-colorable. Xu and Wang (Sci Math 43:15–24, 2013) conjectured that every planar graph without 4- and 6-cycles is 3-colorable. In this paper, we prove that every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1, 1, 0)-colorable, which improves the result of Xu and Wang (Sci Math 43:15–24, 2013), who proved that every planar graph without 4- and 6-cycles is (1, 1, 0)-colorable.
摘要：
Tutte's 3-flow conjecture asserts that every 4-edge-connected graph has a nowhere-zero 3-flow. In this note we prove that every regular graph of valency at least four admitting a solvable arc-transitive group of automorphisms admits a nowhere-zero 3-flow.
摘要：
Let be a 3-edge-connected graph on vertices. It is proved in this paper that if , then either can be -contracted to one of graphs or is one of the graphs in Fig. 1.
摘要：
A (c(1), c(2), ... , c(k))-coloring of G is a mapping phi : V(G) over right arrow {1, 2, ... , k} such that for every i, 1 <= i <= k, G[V-i] has maximum degree at most c1, where G[V-i] denotes the subgraph induced by the vertices colored i. Borodin and Raspaud conjecture that every planar graph without 5-cycles and intersecting triangles is (0, 0, 0)-colorable. We prove in this paper that such graphs are (1, 1, 0)-colorable. (C) 2015 Elsevier B.V. All rights reserved.
摘要：
Jaeger et al. conjectured that every 5-edge-connected graph is Z3-connected. In this paper, we prove that every 4-edge-connected K1,3-free graph without any induced cycle of length at least 5 is Z3-connected, which partially generalizes the earlier results of Lai [Graphs and Combin. 16 (2000) 165-176] and Fukunaga [Graphs and Combin. 27 (2011) 647-659].
摘要：
Jaeger et al. conjectured that every 5-edge-connected graph is Z(3)-connected. In this paper, we prove that every 4-edge-connected K-1,K-3-free graph without any induced cycle of length at least 5 is Z(3)-connected, which partially generalizes the earlier results of Lai [Graphs and Combin. 16 (2000) 165-176] and Fukunaga Graphs and Combin. 27 (2011) 647-659].
摘要：
Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uv ∈ E(G), define d(e) = d(u) + d(v). Let F denote the set of all simple 2-edge-connected graphs on n ≥ 4 vertices such that G ∈ F if and only if d(e) + d(e’) ≥ 2n for every pair of independent edges e, e’ of G. We prove in this paper that for each G ∈ F, G is not Z
3-connected if and only if G is one of K
2,n−2, K
3,n−3, K
2,−2
+
, K
3,−3
+
or one of the 16 specified graphs, which generalizes the results of X. Zhang et al. [Discrete Math., 2010, 310: 3390–3397] and G. Fan and X. Zhou [Discrete Math., 2008, 308: 6233–6240].
作者机构：
[Li, Xiangwen] Cent China Normal Univ, Dept Math, Wuhan 430079, Peoples R China.;Cent China Normal Univ, Hubei Key Lab Math Sci, Wuhan 430079, Peoples R China.
通讯机构：
[Li, Xiangwen] C;Cent China Normal Univ, Dept Math, Wuhan 430079, Peoples R China.
摘要：
Jaeger etźal.'s Z 3 -connectivity conjecture can be reduced to a consideration of 5-edge-connected K 1 , 3 -free graphs by Lovász etźal. (2013) and Ma etźal. (2014). Let K 1 , 3 + denote the graph obtained from K 1 , 3 by adding an edge connecting two vertices of degree 1. Denote by K 1 , 3 ź the graph obtained from a K 1 , 3 + by adding an edge to one vertex of degree 1. In this paper, we will prove the following two results.(1) If G is a 2-connected { K 1 , 3 , K 1 , 3 + } -free simple graph, then G is Z 3 -connected if and only if G is not one of K 4 , K 4 - or an n -cycle, where n ź 3 .(2) If G is a 2-connected { K 1 , 3 , K 1 , 3 ź } -free simple graph, then G is not Z 3 -connected if and only if G is isomorphic to one of the 20 specified graphs or G is an n -cycle, where n ź 3 . Jaeger etźal.'s Z 3 -connectivity conjecture can be reduced to a consideration of 5-edge-connected K 1 , 3 -free graphs by Lovász etźal. (2013) and Ma etźal. (2014). Let K 1 , 3 + denote the graph obtained from K 1 , 3 by adding an edge connecting two vertices of degree 1. Denote by K 1 , 3 ź the graph obtained from a K 1 , 3 + by adding an edge to one vertex of degree 1. In this paper, we will prove the following two results.(1) If G is a 2-connected { K 1 , 3 , K 1 , 3 + } -free simple graph, then G is Z 3 -connected if and only if G is not one of K 4 , K 4 - or an n -cycle, where n ź 3 .(2) If G is a 2-connected { K 1 , 3 , K 1 , 3 ź } -free simple graph, then G is not Z 3 -connected if and only if G is isomorphic to one of the 20 specified graphs or G is an n -cycle, where n ź 3 .
摘要：
Let G and H be two graphs. The semistrong product G o H is the graph with vertex set V(G.H) = V(G)xV(H) and edge set E(G.H) = {(u(1), v(1))(u(2), v(2))vertical bar u(1)u(2) is an element of E(G) and v(1)v(2) is an element of E(H) or u(1) = u(2) and v(1)v(2) is an element of E(H)}. It is proved in this paper that if G and H are two nontrivial connected simple graphs, then G . H admits a nowhere-zero 3-flow. This result extends the study of nowhere-zero flows on product graphs by Emrich and krekovski, by Shu and Zhang, by Rollova and koviera, and by others. (C) 2015 Elsevier B.V. All rights reserved.
