Search

The well-known 5-flow Conjecture of Tutte, stated originally for integer flows, claims that every bridgeless graph has circular flow number at most 5. It is a classical result that the study of the 5-flow Conjecture can be reduced to cubic graphs, in particular to snarks. However, very few procedures to construct snarks with circular flow number 5 are known. In the first part of this paper, we summarise some of these methods and we propose new ones based on variations of the known constructions. Afterwards, we prove that all such methods are nothing but particular instances of a more general construction that we introduce into detail. In the second part, we consider many instances of this general method and we determine when our method permits to obtain a snark with circular flow number 5. Finally, by a computer search, we determine all snarks having circular flow number 5 up to 36 vertices. It turns out that all such snarks of order at most 34 can be obtained by using our method, and that the same holds for 96 of the 98 snarks of order 36 with circular flow number 5., 27 pages; submitted for publication

The Berge-Fulkerson conjecture, originally formulated in the language of mathematical programming, asserts that the edges of every bridgeless cubic ( 3 3 -valent) graph can be covered with six perfect matchings in such a way that every edge is in exactly two of them. As with several other classical conjectures in graph theory, every counterexample to the Berge-Fulkerson conjecture must be a non- 3 3 -edge-colorable cubic graph. In contrast to Tutte’s 5-flow conjecture and the cycle double conjecture, no nontrivial reduction is known for the Berge-Fulkerson conjecture. In the present paper, we prove that a possible minimum counterexample to the conjecture must be cyclically 5 5 -edge-connected.

In an edge-coloring of a cubic graph, an edge is poor or rich, if the set of colors assigned to the edge and the four edges adjacent it, has exactly five or exactly three distinct colors, respectively. An edge is normal in an edge-coloring if it is rich or poor in this coloring. A normal $k$-edge-coloring of a cubic graph is an edge-coloring with $k$ colors such that each edge of the graph is normal. We denote by $\chi'_{N}(G)$ the smallest $k$, for which $G$ admits a normal $k$-edge-coloring. Normal edge-colorings were introduced by Jaeger in order to study his well-known Petersen Coloring Conjecture. It is known that proving $\chi'_{N}(G)\leq 5$ for every bridgeless cubic graph is equivalent to proving Petersen Coloring Conjecture. Moreover, Jaeger was able to show that it implies classical conjectures like Cycle Double Cover Conjecture and Berge-Fulkerson Conjecture. Recently, two of the authors were able to show that any simple cubic graph admits a normal $7$-edge-coloring, and this result is best possible. In the present paper, we show that any claw-free bridgeless cubic graph, permutation snark, tree-like snark admits a normal $6$-edge-coloring. Finally, we show that any bridgeless cubic graph $G$ admits a $6$-edge-coloring such that at least $\frac{7}{9}\cdot |E|$ edges of $G$ are normal., Comment: 17 pages, 11 figures. arXiv admin note: text overlap with arXiv:1804.09449

Given an edge-coloring of a graph $G$, we associate to every vertex $v$ of $G$ the set of colors appearing on the edges incident with $v$. The palette index of $G$ is defined as the minimum number of such distinct sets, taken over all possible edge-colorings of $G$. A graph with a small palette index admits an edge-coloring which can be locally considered to be almost symmetric, since few different sets of colors appear around its vertices. Graphs with palette index $1$ are $r$-regular graphs admitting an $r$-edge-coloring, while regular graphs with palette index $2$ do not exist. Here, we characterize all graphs with palette index either $2$ or $3$ in terms of the existence of suitable decompositions in regular subgraphs. As a corollary, we obtain a complete characterization of regular graphs with palette index $3$., Comment: 14 pages, 5 figures

If $f:\mathbb{N}\rightarrow \mathbb{N}$ is a function, then let us say that $f$ is sublinear if \[\lim_{n\rightarrow +\infty}\frac{f(n)}{n}=0.\] If $G=(V,E)$ is a cubic graph and $c:E\rightarrow \{1,...,k\}$ is a proper $k$-edge-coloring of $G$, then an edge $e=uv$ of $G$ is poor (rich) in $c$, if the edges incident to $u$ and $v$ are colored with three (five) colors. An edge is abnormal if it is neither rich nor poor. The Petersen coloring conjecture of Jaeger states that any bridgeless cubic graph admits a proper 5-edge-coloring $c$, such that there is no an abnormal edge of $G$ with respect to $c$. For a proper 5-edge-coloring $c$ of $G$, let $N_G(c)$ be the set of abnormal edges of $G$ with respect to $c$. In this paper we show that (a) The Petersen coloring conjecture is equivalent to the statement that there is a sublinear function $f:\mathbb{N}\rightarrow \mathbb{N}$, such that all bridgeless cubic graphs admit a proper 5-edge-coloring $c$ with $|N_G(c)|\leq f(|V|)$; (b) for $k=2,3,4$, the statement that there is a sublinear function $f:\mathbb{N}\rightarrow \mathbb{N}$, such that all (cyclically) $k$-edge-connected cubic graphs admit a proper 5-edge-coloring $c$ with $|N_G(c)|\leq f(|V|)$ is equivalent to the statement that all (cyclically) $k$-edge-connected cubic graphs admit a proper 5-edge-coloring $c$ with $|N_G(c)|\leq 2k+1$., 10 pages, 4 figures

Let G be a finite graph (without loops and multiple edges) and let w : E ( G ) → [ 0 , + ∞ ) be a weight function on the edge set of G . We consider the ratio between the maximum weight of a perfect matching of G and the maximum weight of a matching of G . The parameter η ( G ) , introduced by Brazil & al. in Brazil et al. (2016), is defined as the minimum of such a ratio among all nonnegative edge weight assignments of G . In the present paper, we propose a way to compute a lower bound for the parameter η ( G ) , and we use it to prove that for every rational number q in the interval [ 0 , 1 ] there exists a graph G such that η ( G ) = q . Moreover, we further use the same method, in combination with some new arguments, to establish the value of η for Prism graphs and Mobius Ladders. Finally, we improve known results for Blanusa Snarks B 1 and B 2 by determining the exact value of η ( B 1 ) and η ( B 2 ) .

A normal $k$-edge-coloring of a cubic graph is an edge-coloring with $k$ colors having the additional property that when looking at the set of colors assigned to any edge $e$ and the four edges adjacent it, we have either exactly five distinct colors or exactly three distinct colors. We denote by $\chi'_{N}(G)$ the smallest $k$, for which $G$ admits a normal $k$-edge-coloring. Normal $k$-edge-colorings were introduced by Jaeger in order to study his well-known Petersen Coloring Conjecture. More precisely, it is known that proving $\chi'_{N}(G)\leq 5$ for every bridgeless cubic graph is equivalent to proving Petersen Coloring Conjecture and then, among others, Cycle Double Cover Conjecture and Berge-Fulkerson Conjecture. Considering the larger class of all simple cubic graphs (not necessarily bridgeless), some interesting questions naturally arise. For instance, there exist simple cubic graphs, not bridgeless, with $\chi'_{N}(G)=7$. On the other hand, the known best general upper bound for $\chi'_{N}(G)$ was $9$. Here, we improve it by proving that $\chi'_{N}(G)\leq7$ for any simple cubic graph $G$, which is best possible. We obtain this result by proving the existence of specific no-where zero $\mathbb{Z}_2^2$-flows in $4$-edge-connected graphs., Comment: 17 pages, 6 figures

In 1994, it was conjectured by Fan and Raspaud that every simple bridgeless cubic graph has three perfect matchings whose intersection is empty. In this paper we answer a question recently proposed by Mkrtchyan and Vardanyan, by giving an equivalent formulation of the Fan-Raspaud Conjecture. We also study a possibly weaker conjecture originally proposed by the first author, which states that in every simple bridgeless cubic graph there exist two perfect matchings such that the complement of their union is a bipartite graph. Here, we show that this conjecture can be equivalently stated using a variant of Petersen-colourings, we prove it for graphs having oddness at most four and we give a natural extension to bridgeless cubic multigraphs and to certain cubic graphs having bridges., 17 pages, 11 figures

It is well known that the circular flow number of a bridgeless cubic graph can be computed in terms of certain partitions of its vertex set with prescribed properties. In the present paper, we first study some of these properties that turn out to be useful in order to make an efficient and practical implementation of an algorithm for the computation of the circular flow number of a bridgeless cubic graph. Using this procedure, we determine the circular flow number of all snarks on up to 36 vertices as well as the circular flow number of various famous snarks. After that, as combination of the use of this algorithm with new theoretical results, we present an infinite family of snarks of order 8 k + 2 whose circular flow numbers meet a general lower bound presented by Lukot’ka and Skoviera in 2008. In particular this answers a question proposed in their paper. Moreover, we improve the best known upper bound for the circular flow number of Goldberg snarks and we conjecture that this new upper bound is optimal.

A $k$-weak bisection of a cubic graph $G$ is a partition of the vertex-set of $G$ into two parts $V_1$ and $V_2$ of equal size, such that each connected component of the subgraph of $G$ induced by $V_i$ ($i=1,2$) is a tree of at most $k-2$ vertices. This notion can be viewed as a relaxed version of nowhere-zero flows, as it directly follows from old results of Jaeger that every cubic graph $G$ with a circular nowhere-zero $r$-flow has a $\lfloor r \rfloor$-weak bisection. In this paper we study problems related to the existence of $k$-weak bisections. We believe that every cubic graph which has a perfect matching, other than the Petersen graph, admits a 4-weak bisection and we present a family of cubic graphs with no perfect matching which do not admit such a bisection. The main result of this article is that every cubic graph admits a 5-weak bisection. When restricted to bridgeless graphs, that result would be a consequence of the assertion of the 5-flow Conjecture and as such it can be considered a (very small) step toward proving that assertion. However, the harder part of our proof focuses on graphs which do contain bridges.

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.

A graph admitting a perfect matching has the Perfect-Matching-Hamiltonian property (for short the PMH-property) if each of its perfect matchings can be extended to a Hamiltonian cycle. In this paper we establish some sufficient conditions for a graph $G$ in order to guarantee that its line graph $L(G)$ has the PMH-property. In particular, we prove that this happens when $G$ is (i) a Hamiltonian graph with maximum degree at most $3$, (ii) a complete graph, or (iii) an arbitrarily traceable graph. Further related questions and open problems are proposed along the paper., Comment: 12 pages, 4 figures

Brualdi and Hollingsworth conjectured in Brualdi and Hollingsworth (1996) that in any complete graph K 2 n , n ≥ 3 , which is properly colored with 2 n − 1 colors, the edge set can be partitioned into n edge disjoint rainbow spanning trees (where a graph is said to be rainbow if its edges have distinct colors). Constantine (2002) strengthened this conjecture asking the rainbow spanning trees to be pairwise isomorphic. He also showed an example satisfying his conjecture for every 2 n ∈ { 2 s : s ≥ 3 } ∪ { 5 ⋅ 2 s , s ≥ 1 } . Caughmann, Krussel and Mahoney (2017) recently showed a first infinite family of edge colorings for which the conjecture of Brualdi and Hollingsworth can be verified. In the present paper, we extend this result to all edge-colorings arising from cyclic 1-factorizations of K 2 n constructed by Hartman and Rosa (1985). Finally, we remark that our constructions permit to extend Constatine’s result also to all 2 n ∈ { 2 s d : s ≥ 1 , d > 3 odd } .

Given a proper edge-coloring of a loopless multigraph, the palette of a vertex is defined as the set of colors of the edges which are incident with it. The palette index of a multigraph is defined as the minimum number of distinct palettes occurring among the vertices, taken over all proper edge-colorings of the multigraph itself. In this framework, the palette multigraph of an edge-colored multigraph is defined in this paper and some of its properties are investigated. We show that these properties can be applied in a natural way in order to produce the first known family of multigraphs whose palette index is expressed in terms of the maximum degree by a quadratic polynomial. We also attempt an analysis of our result in connection with some related questions., 13 pages, 2 figures

There are many hard conjectures in graph theory, like Tutte's 5-flow conjecture, and the $5$-cycle double cover conjecture, which would be true in general if they would be true for cubic graphs. Since most of them are trivially true for $3$-edge-colorable cubic graphs, cubic graphs which are not $3$-edge-colorable, often called snarks, play a key role in this context. Here, we survey parameters measuring how far apart a non $3$-edge-colorable graph is from being $3$-edge-colorable. We study their interrelation and prove some new results. Besides getting new insight into the structure of snarks, we show that such measures give partial results with respect to these important conjectures. The paper closes with a list of open problems and conjectures.

Given two positive integers l and m , with l ? m , an l , m ] -covering of a graph G is a set M of matchings of G whose union is the edge set of G and such that l ? | M | ? m for every M ? M .An l , m ] -covering M of G is an excessive l , m ] -factorization of G if the cardinality of M is as small as possible. The number of matchings in an excessive l , m ] -factorization of G (or ∞ , if G does not admit an excessive l , m ] -factorization) is a graph parameter called the excessive l , m ] -index of G and denoted by ? l , m ] ' ( G ) . In this paper we study such parameter. Our main result is a general formula for the excessive l , m ] -index of a graph G in terms of other graph parameters. Furthermore, we give a polynomial time algorithm which computes ? l , m ] ' ( G ) for any fixed constants l and m and outputs an excessive l , m ] -factorization of G , whenever the latter exists.

We prove that every cyclically 6-edge-connected cubic graph with oddness at most 4 has a nowhere-zero 5-flow. Therefore, a possible minimum counterexample to the 5-flow conjecture has oddness at least 6.

A k -bisection of a bridgeless cubic graph G is a 2-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 have order at most k . Ban and Linial conjectured that every bridgeless cubic graph admits a 2-bisection except for the Petersen graph. In this note, we prove Ban–Linial’s conjecture for claw-free cubic graphs.

The excessive m ] -index of a graph G , denoted by ? m ] ' ( G ) , is the minimum number of matchings of size m needed to cover the edge-set of G . We set ? m ] ' ( G ) = ∞ if such a cover does not exist and we call a graph G m ] -coverable if its excessive m ] -index is finite. Obviously ? 1 ] ' ( G ) = | E ( G ) | and it is easy to prove for a 2 ] -coverable graph G that ? 2 ] ' ( G ) = max { ? ' ( G ) , ? | E ( G ) | / 2 ? } holds, where ? ' ( G ) denotes the chromatic index of G . The case m = 3 is completely solved in Cariolaro and Fu (2009)? 4]. In this paper we prove a general formula for computing the excessive 4 ] -index of a tree and we conjecture a possible generalization for any value of m . Furthermore, we prove that such a formula does not work for the excessive 4 ] -index of an arbitrary graph.

We propose three new conjectures on perfect matchings in cubic graphs. The weakest conjecture is implied by a well-known conjecture of Berge and Fulkerson. The other two conjectures are a strengthening of the first one. All conjectures are trivially verified for 3-edge-colorable cubic graphs and by computer for all snarks of order at most 34.

Let G be a bridgeless cubic graph. Fulkerson conjectured that there exist six 1-factors of G such that each edge of G is contained in exactly two of them. Berge conjectured that the edge-set of G can be covered with at most five 1-factors. We prove that the two conjectures are equivalent. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:125-128, 2011 © 2011 Wiley Periodicals, Inc.

Let F be a 2-factorization of the complete graph Kv admitting an automorphism group G acting doubly transitively on the set of factors. In the Hamiltonian case the only possibility is the unique factorization of K5, while in the non-Hamiltonian case we give some classes of examples and some necessary conditions for the existence of such factorizations.

A total coloring is equitable if the number of elements colored with each color differs by at most one, and the least integer for which a graph has such a coloring is called its equitable total chromatic number. Wang conjectured that the equitable total chromatic number of a multigraph of maximum degree is at most + 2 , and proved this for the case where 3 . Therefore, the equitable total chromatic number of a cubic graph is either 4 or 5, and in this work we prove that the problem of deciding whether it is 4 is NP-complete for bipartite cubic graphs.Furthermore, we present the first known Type1 cubic graphs with equitable total chromatic number5. All of them have, by construction, a small girth. We also find one infinite family of Type1 cubic graphs of girth5 having equitable total chromatic number 4. This motivates the following question: Does there exist Type1 cubic graphs of girth greater than5 and equitable total chromatic number5?

For some time the Petersen graph has been the only known Snark with circular flow number $5$ (or more, as long as the assertion of Tutte's $5$-flow Conjecture is in doubt). Although infinitely many such snarks were presented eight years ago by Macajova and Raspaud, the variety of known methods to construct them and the structure of the obtained graphs were still rather limited. We start this article with an analysis of sets of flow values, which can be transferred through flow networks with the flow on each edge restricted to the open interval $(1,4)$ modulo $5$. All these sets are symmetric unions of open integer intervals in the ring $\mathbb{R}/5\mathbb{Z}$. We use the results to design an arsenal of methods for constructing snarks $S$ with circular flow number $\phi_c(S)\ge 5$. As one indication to the diversity and density of the obtained family of graphs, we show that it is sufficiently rich so that the corresponding recognition problem is NP-complete., Comment: 30 pages - revised version

A proper edge-coloring of a graph G is an assignment of colors to the edges of G such that adjacent edges receive distinct colors. A proper edge-coloring defines at each vertex the set of colors of its incident edges. Following the terminology introduced by Hor?ak, Kalinowski, Meszka and Wo?niak, we call such a set of colors the palette of the vertex. What is the minimum number of distinct palettes taken over all proper edge-colorings of G? A complete answer is known for complete graphs and cubic graphs. We study in some detail the problem for 4-regular graphs. In particular, we show that certain values of the palette index imply the existence of an even cycle decomposition of size 3 (a partition of the edge-set of a graph into 3 2-regular subgraphs whose connected components are cycles of even length). This result can be extended to 4d-regular graphs. Moreover, in studying the palette index of a 4-regular graph, the following problem arises: does there exist a 4-regular graph whose even cycle decompositions cannot have size smaller than 4?

We study snarks whose edges cannot be covered by fewer than five perfect matchings. Esperet and Mazzuoccolo found an infinite family of such snarks, generalising an example provided by Hagglund. We construct another infinite family, arising from a generalisation in a different direction. The proof that this family has the requested property is computer-assisted. In addition, we prove that the snarks from this family (we call them treelike snarks) have circular flow number five and admit a 5-cycle double cover., Comment: 19 pages, 19 figures

We show that "almost all" generalized Petersen graphs have total chromatic number 4. More precisely: for each integer k ? 2 , there exists an integer N ( k ) such that, for any n ? N ( k ) , the generalized Petersen graph G ( n , k ) has total chromatic number?4.

The automorphic H-chromatic index of a graph Γ is the minimum integer m for which Γ has a proper edge-coloring with m colors preserved by a given subgroup H of the full automorphism group of Γ. We determine upper bounds for this index in terms of the chromatic index of Γ for some abelian 2-groups H.

The problem of establishing the number of perfect matchings necessary to cover the edge-set of a cubic bridgeless graph is strictly related to a famous conjecture of Berge and Fulkerson. In this paper we prove that deciding whether this number is at most 4 for a given cubic bridgeless graph is NP-complete. We also construct an infinite family $\cal F$ of snarks (cyclically 4-edge-connected cubic graphs of girth at least five and chromatic index four) whose edge-set cannot be covered by 4 perfect matchings. Only two such graphs were known. It turns out that the family $\cal F$ also has interesting properties with respect to the shortest cycle cover problem. The shortest cycle cover of any cubic bridgeless graph with $m$ edges has length at least $\tfrac43m$, and we show that this inequality is strict for graphs of $\cal F$. We also construct the first known snark with no cycle cover of length less than $\tfrac43m+2$., Comment: 17 pages, 8 figures

A conjecture of Berge and Fulkerson (1971) states that every cubic bridgeless graph contains 6 perfect matchings covering each edge precisely twice, which easily implies that every cubic bridgeless graph has three perfect matchings with empty intersection (this weaker statement was conjectured by Fan and Raspaud in 1994). Let $m_t$ be the supremum of all reals $\alpha\le 1$ such that for every cubic bridgeless graph $G$, there exist $t$ perfect matchings of $G$ covering a fraction of at least $\alpha$ of the edges of $G$. It is known that the Berge-Fulkerson conjecture is equivalent to the statement that $m_5=1$, and implies that $m_4=\tfrac{14}{15}$ and $m_3=\tfrac45$. In the first part of this paper, we show that $m_4=\tfrac{14}{15}$ implies $m_3=\tfrac45$, and $m_3=\tfrac45$ implies the Fan-Raspaud conjecture, strengthening a recent result of Tang, Zhang, and Zhu. In the second part of the paper, we prove that for any $2\le t \le 4$ and for any real $\tau$ lying in some appropriate interval, deciding whether a fraction of more than (resp. at least) $\tau$ of the edges of a given cubic bridgeless graph can be covered by $t$ perfect matching is an NP-complete problem. This resolves a conjecture of Tang, Zhang, and Zhu., Comment: 13 pages, 5 figures - revised version

Fullerene graphs are trivalent plane graphs with only hexagonal and pentagonal faces. They are often used to model large carbon molecules: each vertex represents a carbon atom and the edges represent chemical bonds. A totally symmetric Kekule structure in a fullerene graph is a set of independent edges which is fixed by all symmetries of the fullerene and molecules with totally symmetric Kekule structures could have special physical and chemical properties, as suggested in [Austin, S.J, and J. Baker, P. W. Fowler, D. E. Manolopoulos, Bond-stretch Isomerism and the Fullerenes, J. Chem. Soc. Perkin Trans. 2 (1994), 2319–2323] and [Rogers, K.M., and P. W. Fowler, Leapfrog fullerenes, Huckel bond order and Kekule structures, J. Chem. Soc. Perkin Trans. 2 (2001), 18–22]. All fullerenes with at least ten symmetries were studied in [Graver, J.E. The Structure of Fullerene Signature, DIMACS Series of Discrete Mathematics and Theoretical Computer Science 64, AMS (2005), 137–166.] and a complete catalog was given in [Graver, J. E. Catalog of All Fullerene with Ten or More Symmetries DIMACS Series of Discrete Mathematics and Theoretical Computer Science 64 AMS (2005), 167–188]. Starting from this catalog in [Bogaerts, M., and G. Mazzuoccolo, G.Rinaldi, Totally symmetric Kekule structures in fullerene graphs with ten or more symmetries, MATCH Communications in Mathematical and in Computer Chemistry 69 (2013), 677–705] we established exactly which of them have at least one totally symmetric Kekule structure.

Let G be a bridgeless cubic graph. A well-known conjecture of Berge and Fulkerson can be stated as follows: there exist five perfect matchings of G such that each edge of G is contained in at least one of them. Here, we prove that in each bridgeless cubic graph there exist five perfect matchings covering a portion of the edges at least equal to 215/231 . By a generalization of this result, we decrease the best known upper bound, expressed in terms of the size of the graph, for the number of perfect matchings needed to cover the edge-set of G., accepted for the publication in Discrete Mathematics

An automorphism group G of a 1-factorization of the complete multipartite graph K m×n consists of permutations of the vertices of the graph mapping factors to factors. In this paper, we give a complete answer to the existence problem of a 1-factorization of K m×n admitting a cyclic or dihedral group acting sharply transitively on the vertices of the graph., info:eu-repo/semantics/published

We show that there exists a family of r-regular graphs of arbitrarily large excessive index for each integer r greater than 3. Furthermore, we answer a question in Bonisoli and Cariolaro (2007) [1] showing that all the positive integers can be attained as excessive classes of regular graphs.

The automorphic G-chromatic index of a graph Γ is the minimum integer m for which Γ has a proper edge-coloring with m colors which is preserved by the full automorphism group G of Γ. We determine the automorphic G-chromatic index of each member of four infinite classes of snarks: type I Blanusa snarks, type II Blanusa snarks, Flower snarks and Goldberg snarks.

In this paper we define the automorphic H-chromatic index of a graph Γ as the minimum integer m for which Γ has a proper edge-coloring with m colors which is preserved by a given automorphism group H of Γ. After the description of some properties, we determine upper bounds for this index when H is a cyclic group of prime order. We also show that these upper bounds are best possible in a number of instances.

Given a finite group $G$ of even order, which graphs $\Gamma$ have a $1$-factorization admitting $G$ as automorphism group with a sharply transitive action on the vertex-set? Starting from this question, we prove some general results and develop an exhaustive analysis when $\Gamma$ is a complete multipartite graph and $G$ is cyclic.

We consider 2-factorizations of complete graphs that possess an automorphism group fixing k⩾0 vertices and acting sharply transitively on the others. We study the structures of such factorizations and consider the cases in which the group is either abelian or dihedral in some more details. Combining results of the first part of the paper with a result of D. Bryant, J Combin Des, 12 (2004), 147–155, we prove that the class of 2-factorizations of complete graphs is universal. Namely each finite group is the full automorphism group of a 2-factorization of the class. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 211-228, 2009

Let be a 2-factorization of the complete graph Kv admitting an automorphism group G acting doubly transitively on the set of vertices. The vertex-set V(Kv) can then be identified with the point-set of AG(n, p) and each 2-factor of is the union of p-cycles which are obtained from a parallel class of lines of AG(n, p) in a suitable manner, the group G being a subgroup of A G L(n, p) in this case. The proof relies on the classification of 2-(v, k, 1) designs admitting a doubly transitive automorphism group. The same conclusion holds even if G is only assumed to act doubly homogeneously. © 2006 Wiley Periodicals, Inc. J Combin Designs

We consider one–factorizations of complete graphs which possess an automorphism group fixing k ≥ 0 vertices and acting regularly (i.e., sharply transitively) on the others. Since the cases k = 0 and k = 1 are well known in literature, we study the case k≥ 2 in some detail. We prove that both k and the order of the group are even and the group necessarily contains k − 1 involutions. Constructions for some classes of groups are given. In particular we extend the result of [7]: let G be an abelian group of even order and with k − 1 involutions, a one–factorization of a complete graph admitting G as an automorphism group fixing k vertices and acting regularly on the others can be constructed.

We consider 2-factorizations of the complete graph K v whose automorphism group is “rich” in some sense. In particular we show the results obtained when the automorphism group acts 2-transitively either on the vertices of K v or on the set of factors.

Given a graph G, an automorphic edge(vertex)-coloring of G is a proper edge(vertex)-coloring such that each automorphism of the graph preserves the coloring. The automorphic chromatic index (number) is the least integer k for which G admits an automorphic edge(vertex)coloring with k colors. We show that it is NP-complete to determine the automorphic chromatic index and the automorphic chromatic number of an arbitrary graph.

For each finitely generated abelian infinite group G, we construct a 1-factorization of the countable complete graph admitting G as an automorphism group acting sharply transitively on vertices.

Let F be a 2-factorization of the complete graph Kv admitting an automorphism group G acting primitively on the set of vertices. If F consists of Hamiltonian cycles, then F is the unique, up to isomorphisms, 2-factorization of Kpn admitting an automorphism group which acts 2-transitively on the vertex-set, see [A. Bonisoli, M. Buratti, G. Mazzuoccolo, Doubly transitive 2-factorizations, J. Combin. Designs 15 (2007) 120–132.]. In the non-Hamiltonian case we construct an infinite family of examples whose automorphism group does not contain a subgroup acting 2-transitively on vertices.