Compact cyclic edge-colorings of graphs

The paper is devoted to a model of compact cyclic edge-coloring of graphs. This variant of edge-coloring finds its applications in modeling schedules in production systems, in which production proceeds in a cyclic way. We point out optimal colorings for some graph classes and we construct graphs which cannot be colored in a compact cyclic manner. Moreover, we prove some theoretical properties of considered coloring model such as upper bounds on the number of colors in optimal compact cyclic coloring.     

图的区间边着色的收缩图方法

图G的一个用了颜色1,2,…,t的边着色称为区间t-着色,如果所有t种颜色都被用到,并且关联于G的同一个顶点的边上的颜色是各不相同的,且这些颜色构成了一个连续的整数区间.G称作是可区间着色的,如果对某个正整数t,G有一个区间t-着色.所有可区间着色的图构成的集合记作■.对图G∈■,使得G有一个区间t-着色的t的最小值和最大值分别记作ω(G)和W(G).现给出了图的区间着色的收缩图方法.利用此方法,我们对双圈图G∈■,证明了ω(G)=△(G)或△(G)+1,并且完全确定了ω(G)=△(G)及ω(G)=△(G)+1的双圈图类.     

A generalization of interval edge-colorings of graphs

An edge-coloring of a graph G with colors 1,2,…,t is called an interval (t,1)-coloring if at least one edge of G is colored by i, i=1,2,…,t, and the colors of edges incident to each vertex of G are distinct and form an interval of integers with no more than one gap. In this paper we investigate some properties of interval (t,1)-colorings. We also determine exact values of the least and the greatest possible number of colors in such colorings for some families of graphs.     

Path factors in cubic graphs

Let ? be a set of connected graphs. An ?‐factor of a graph is its spanning subgraph such that each component is isomorphic to one of the members in ?. Let P_k denote the path of order k. Akiyama and Kano have conjectured that every 3‐connected cubic graph of order divisible by 3 has a {P₃}‐factor. Recently, Kaneko gave a necessary and sufficient condition for a graph to have a {P₃, P₄, P₅}‐factor. As a corollary, he proved that every cubic graph has a {P₃, P₄, P₅}‐factor. In this paper, we prove that every 2‐connected cubic graph of order at least six has a {P_k ∣ k ≥ , 6}‐factor, and hence has a {P₃, P₄}‐factor. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 188–193, 2002; DOI 10.1002/jgt.10022     

Classifying cubic symmetric graphs of order 10p or 10p~2

A graph is called s-regular if its automorphism group acts regularly on the set of its s-arcs. In this paper, the s-regular cyclic or elementary abelian coverings of the Petersen graph for each s ≥ 1 are classified when the fibre-preserving automorphism groups act arc-transitively. As an application of these results, all s-regular cubic graphs of order 10p or 10p2 are also classified for each s ≥ 1 and each prime p, of which the proof depends on the classification of finite simple groups.     

Optimal acyclic edge‐coloring of cubic graphs

An acyclic edge‐coloring of a graph is a proper edge‐coloring such that the subgraph induced by the edges of any two colors is acyclic. The acyclic chromatic index of a graph G is the smallest number of colors in an acyclic edge‐coloring of G. We prove that the acyclic chromatic index of a connected cubic graph G is 4, unless G is K₄ or K_3,3; the acyclic chromatic index of K₄ and K_3,3 is 5. This result has previously been published by Fiam?ík, but his published proof was erroneous.     

Nowhere‐zero flows in tensor product of graphs

In this paper, we characterize graphs whose tensor product admit nowhere‐zero 3‐flow. The main result is: For two graphs G₁ and G₂ with δ ≥ 2 and G₂ not belonging to a well‐characterized class of graphs, the tensor product of G₁ and G₂ admits a nowhere‐zero 3‐flow. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 284–292, 2007     

Decomposing planar cubic graphs

The 3‐Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2‐regular subgraph and a matching. We show that this conjecture holds for the class of connected plane cubic graphs.     

Change graphs of edge-colorings of planar cubic graphs

It will be proved that the number of vertices of each component of the change-graph of two edge-colorings of an arbitrary planar cubic graph is even (here a change-graph is the subgraph containing exactly those edges having different colors in the considered two edge-colorings and moreover only those vertices which are incident with at least one of these edges).     

On incidence choosability of cubic graphs

An incidence of a graph $G$ is a pair $(u,e)$ where $u$ is a vertex of $G$ and $e$ is an edge of $G$ incident to $u$. Two incidences $(u,e)$ and $(v,f)$ of $G$ are adjacent whenever (i) $u=v$, or (ii) $e=f$, or (iii) $uv=e$ or $uv=f$. An incidence$k$-coloring of $G$ is a mapping from the set of incidences of $G$ to a set of $k$ colors such that every two adjacent incidences receive distinct colors. The notion of incidence coloring has been introduced by Brualdi and Quinn Massey (1993) from a relation to strong edge coloring, and since then, has attracted a lot of attention by many authors.On a list version of incidence coloring, it was shown by Benmedjdoub et al. (2017) that every Hamiltonian cubic graph is incidence 6-choosable. In this paper, we show that every cubic (loopless) multigraph is incidence 6-choosable. As a direct consequence, it implies that the list strong chromatic index of a $(2,3)$-bipartite graph is at most 6, where a (2,3)-bipartite graph is a bipartite graph such that one partite set has maximum degree at most 2 and the other partite set has maximum degree at most 3.     

A Steiner triple system which colors all cubic graphs

We prove that there is a Steiner triple system ?? such that every simple cubic graph can have its edges colored by points of ?? in such a way that for each vertex the colors of the three incident edges form a triple in ??. This result complements the result of Holroyd and ?koviera that every bridgeless cubic graph admits a similar coloring by any Steiner triple system of order greater than 3. The Steiner triple system employed in our proof has order 381 and is probably not the smallest possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 15–24, 2004     

Complexity of two coloring problems in cubic planar bipartite mixed graphs

In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs, which arise from scheduling problems where disjunctive and precedence constraints have to be taken into account. We show that they are both NP-complete in cubic planar bipartite mixed graphs, which strengthens some results of Ries and de Werra (2008) [9].     

Nowhere‐Zero Flows on Signed Complete and Complete Bipartite Graphs

Bouchet's conjecture asserts that each signed graph which admits a nowhere‐zero flow has a nowhere‐zero 6‐flow. We verify this conjecture for two basic classes of signed graphs—signed complete and signed complete bipartite graphs by proving that each such flow‐admissible graph admits a nowhere‐zero 4‐flow and we characterise those which have a nowhere‐zero 2‐flow and a nowhere‐zero 3‐flow.     

List total colorings of series-parallel graphs

A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring. In this paper, we first show that the list total coloring problem is NP-complete even for series-parallel graphs. We then give a sufficient condition for a series-parallel graph to have a list total coloring, that is, we prove a theorem that any series-parallel graph G has a list total coloring if |L(v)|min{5,Δ+1} for each vertex v and |L(e)|max{5,d(v)+1,d(w)+1} for each edge e=vw, where Δ is the maximum degree of G and d(v) and d(w) are the degrees of the ends v and w of e, respectively. The theorem implies that any series-parallel graph G has a total coloring with Δ+1 colors if Δ4. We finally present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G satisfies the sufficient condition.     

Nowhere‐Zero 5‐Flows On Cubic Graphs with Oddness 4

Tutte's 5‐flow conjecture from 1954 states that every bridgeless graph has a nowhere‐zero 5‐flow. It suffices to prove the conjecture for cyclically 6‐edge‐connected cubic graphs. We prove that every cyclically 6‐edge‐connected cubic graph with oddness at most 4 has a nowhere‐zero 5‐flow. This implies that every minimum counterexample to the 5‐flow conjecture has oddness at least 6.     

Normal Cayley graphs of finite groups

LetG be a finite group and let S be a nonempty subset of G not containing the identity element 1. The Cayley (di) graph X = Cay(G, S) of G with respect to S is defined byV (X)=G, E (X)={(g,sg)|g∈G, s∈S} A Cayley (di) graph X = Cay (G,S) is said to be normal ifR(G) ◃A = Aut (X). A group G is said to have a normal Cayley (di) graph if G has a subset S such that the Cayley (di) graph X = Cay (G, S) is normal. It is proved that every finite group G has a normal Cayley graph unlessG≅ℤ₄×ℤ₂ orG≅Q ₈×ℤ ₂ ^r (r⩾0) and that every finite group has a normal Cayley digraph, where Z_m is the cyclic group of orderm and Q₈ is the quaternion group of order 8. Project supported by the National Natural Science Foundation of China (Grant No. 10231060) and the Doctorial Program Foundation of Institutions of Higher Education of China.     

List edge and list total coloring of 1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that each 1-planar graph with maximum degree Δ is (Δ+1)-edge-choosable and (Δ+2)- total-choosable if Δ≥16, and is Δ-edge-choosable and (Δ+1)-total-choosable if Δ≥21. The second conclusion confirms the list coloring conjecture for the class of 1-planar graphs with large maximum degree.     

Colourings of cubic graphs inducing isomorphic monochromatic subgraphs

A -bisection of a bridgeless cubic graph is a -colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes ( monochromatic components in what follows) have order at most . Ban and Linial Conjectured that every bridgeless cubic graph admits a -bisection except for the Petersen graph. A similar problem for the edge set of cubic graphs has been studied: Wormald conjectured that every cubic graph with has a -edge colouring such that the two monochromatic subgraphs are isomorphic linear forests (ie, a forest whose components are paths). Finally, Ando conjectured that every cubic graph admits a bisection such that the two induced monochromatic subgraphs are isomorphic. In this paper, we provide evidence of a strong relation of the conjectures of Ban-Linial and Wormald with Ando's Conjecture. Furthermore, we also give computational and theoretical evidence in their support. As a result, we pose some open problems stronger than the above-mentioned conjectures. Moreover, we prove Ban-Linial's Conjecture for cubic-cycle permutation graphs. As a by-product of studying -edge colourings of cubic graphs having linear forests as monochromatic components, we also give a negative answer to a problem posed by Jackson and Wormald about certain decompositions of cubic graphs into linear forests.     

Circular edge-colorings of cubic graphs with girth six

We show that the circular chromatic index of a (sub)cubic graph with girth at least six is at most 7/2.