共查询到20条相似文献,搜索用时 46 毫秒
1.
Ulrike Baumann 《Mathematische Nachrichten》1993,163(1):93-100
A perfect colouring Φ of a simple undirected connected graph G is an edge colouring such that each vertex is incident with exactly one edge of each colour. This paper concerns the problem of representing groups by graphs with perfect colourings. We define groups of graph automorphisms, which preserve the structure of the colouring, and characterize these groups up to isomorphism. Our considerations are based on the fact that every perfectly coloured graph is isomorphic to a Schreier coset graph on a group generated by involutions. 相似文献
2.
An edge-coloured graph G is a vertex set V(G) together with m edge sets distinguished by m colours. Let π be a permutation on {1,2,…,m}. We define a switching operation consisting of π acting on the edge colours similar to Seidel switching, to switching classes as studied by Babai and Cameron, and to the pushing operation studied by Klostermeyer and MacGillivray. An edge-coloured graph G is π-permutably homomorphic (respectively π-permutably isomorphic) to an edge-coloured graph H if some sequence of switches on G produces an edge-coloured graph homomorphic (respectively isomorphic) to H. We study the π-homomorphism and π-isomorphism operations, relating them to homomorphisms and isomorphisms of a constructed edge-coloured graph that we introduce called a colour switching graph. Finally, we identify those edge-coloured graphs H with the property that G is homomorphic to H if and only if any switch of G is homomorphic to H. It turns out that such an H is precisely a colour switching graph. As a corollary to our work, we settle an open problem of Klostermeyer and MacGillivray. 相似文献
3.
A proper vertex colouring of a 2-connected plane graph G is a parity vertex colouring if for each face f and each colour c, either no vertex or an odd number of vertices incident with f is coloured with c. The minimum number of colours used in such a colouring of G is denoted by χp(G).In this paper, we prove that χp(G)≤118 for every 2-connected plane graph G. 相似文献
4.
《Quaestiones Mathematicae》2013,36(4):537-548
AbstractFor a set F of graphs and a natural number k, an (F, k)-colouring of a graph G is a proper colouring of V (G) such that no subgraph of G isomorphic to an element of F is coloured with at most k colours. Equivalently, if P is the class of all graphs that do not contain an element of F as a subgraph, a χP,k colouring of G is a proper colouring such that the union of at most k colour classes induces a graph in P. The smallest number of colours in such a colouring of G, if it exists, is denoted by χP,k (G). We give some general results on χP,k-colourings and investigate values of χP,k (G) for some choices of P and classes of graphs G. 相似文献
5.
A proper edge colouring of a graph G is neighbour-distinguishing provided that it distinguishes adjacent vertices by sets of colours of their incident edges.
It is proved that for any planar bipartite graph G with Δ(G)≥12 there is a neighbour-distinguishing edge colouring of G using at most Δ(G)+1 colours. Colourings distinguishing pairs of vertices that satisfy other requirements are also considered. 相似文献
6.
A rainbow subgraph in an edge-coloured graph is a subgraph such that its edges have distinct colours. The minimum colour degree of a graph is the smallest number of distinct colours on the edges incident with a vertex over all vertices. Kostochka, Pfender, and Yancey showed that every edge-coloured graph on n vertices with minimum colour degree at least k contains a rainbow matching of size at least k, provided ${n\geq \frac{17}{4}k^2}$ . In this paper, we show that n ≥ 4k ? 4 is sufficient for k ≥ 4. 相似文献
7.
Hall's condition is a simple requirement that a graph G and list assignment L must satisfy if G is to have a proper L‐colouring. The Hall number of G is the smallest integer m such that whenever the lists on the vertices each has size at least m and Hall's condition is satisfied a proper L‐colouring exists. Hilton and P.D. Johnson introduced the parameter and showed that a graph has Hall number 1 if and only if every block is a clique. In this paper we give a forbidden‐induced‐subgraph characterization of graphs with Hall number 2. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 81–100, 2004 相似文献
8.
Louigi Addario-Berry Ketan Dalal Colin McDiarmid Bruce A. Reed Andrew Thomason 《Combinatorica》2007,27(1):1-12
A weighting w of the edges of a graph G induces a colouring of the vertices of G where the colour of vertex v, denoted cv, is
. We show that the edges of every graph that does not contain a component isomorphic to K2 can be weighted from the set {1, . . . ,30} such that in the resulting vertex-colouring of G, for every edge (u,v) of G, cu ≠cv. 相似文献
9.
10.
An automorphism α of a group G is called a weakly power automorphism if it maps every non-periodic subgroup of G onto itself. The aim of this paper is to investigate the behavior of weakly power automorphisms. In particular, among other results, it is proved that all weakly power automorphisms of a soluble non-periodic group G of derived length at most 3 are power automorphisms, i.e. they fix all subgroups of G. This result is best possible, as there exists a soluble non-periodic group of derived length 4 admitting a weakly power automorphism, which is not a power automorphism. 相似文献
11.
M. Hofmeister 《Journal of Graph Theory》1988,12(3):437-444
Any group of automorphisms of a graph G induces a notion of isomorphism between double covers of G. The corresponding isomorphism classes will be counted. 相似文献
12.
A b‐coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b‐chromatic number of a graph G is the largest integer k such that G admits a b‐coloring with k colors. A graph is b‐perfect if the b‐chromatic number is equal to the chromatic number for every induced subgraph of G. We prove that a graph is b‐perfect if and only if it does not contain as an induced subgraph a member of a certain list of 22 graphs. This entails the existence of a polynomial‐time recognition algorithm and of a polynomial‐time algorithm for coloring exactly the vertices of every b‐perfect graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:95–122, 2012 相似文献
13.
Let G be a group. By using a family 𝒜 of subsets of automorphisms of G, we introduced a simple graph Γ𝒜(G), which is a generalization of the non-commuting graph. In this paper, we study the combinatorial properties of Γ𝒜(G). 相似文献
14.
J. A. Bondy 《Journal of Graph Theory》1990,14(2):259-272
A perfect path double cover (PPDC) of a graph G on n vertices is a family ?? of n paths of G such that each edge of G belongs to exactly two members of ?? and each vertex of G occurs exactly twice as an end of a path of ??. We propose and study the conjecture that every simple graph admits a PPDC. Among other things, we prove that every simple 3-regular graph admits a PPDC consisting of paths of length three. 相似文献
15.
Zdenk Ryj
ek 《Journal of Graph Theory》1994,18(5):469-477
We say that G is almost claw-free if the vertices that are centers of induced claws (K1,3) in G are independent and their neighborhoods are 2-dominated. Clearly, every claw-free graph is almost claw-free. It is shown that (i) every even connected almost claw-free graph has a perfect matching and (ii) every nontrivial locally connected K1,4-free almost claw-free graph is fully cycle extendable. 相似文献
16.
A colouring of the vertices of a graph (or hypergraph) G is adapted to a given colouring of the edges of G if no edge has the same colour as both (or all) its vertices. The adaptable chromatic number of G is the smallest integer k such that each edge-colouring of G by colours 1,2,…,k admits an adapted vertex-colouring of G by the same colours 1,2,…,k. (The adaptable chromatic number is just one more than a previously investigated notion of chromatic capacity.) The adaptable chromatic number of a graph G is smaller than or equal to the ordinary chromatic number of G. While the ordinary chromatic number of all (categorical) powers Gk of G remains the same as that of G, the adaptable chromatic number of Gk may increase with k. We conjecture that for all sufficiently large k the adaptable chromatic number of Gk equals the chromatic number of G. When G is complete, we prove this conjecture with k≥4, and offer additional evidence suggesting it may hold with k≥2. We also discuss other products and propose several open problems. 相似文献
17.
A perfect matching covering of a graph G is a set of perfect matchings of G such that every edge of G is contained in at least one member of it. Berge conjectured that every bridgeless cubic graph admits a perfect matching covering of order at most 5 (we call such a collection of perfect matchings a Berge covering of G). A cubic graph G is called a Kotzig graph if G has a 3‐edge‐coloring such that each pair of colors forms a hamiltonian circuit (introduced by R. Häggkvist, K. Markström, J Combin Theory Ser B 96 (2006), 183–206). In this article, we prove that if there is a vertex w of a cubic graph G such that , the graph obtained from by suppressing all degree two vertices is a Kotzig graph, then G has a Berge covering. We also obtain some results concerning the so‐called 5‐even subgraph double cover conjecture. 相似文献
18.
《European Journal of Operational Research》1998,106(1):160-164
The k L-list λ colouring of a graph G is an L-list colouring (with positive integers) where any two colours assigned to adjacent vertices do not belong to a set λ, where the avoided assignments are listed. Moreover, the length of the list L(x), for every vertex x of G, must be less than or equal to a positive integer k, where k is the number of colours. This problem is NP-complete and we present an efficient heuristic algorithm to solve it. A fundamental aspect of the algorithm we developed is a particular technique of backtracking that permits the direct reassignment of the vertices causing the conflict if, at the moment of assigning a colour to a vertex, no colour on the list associated to it is available. An application of this algorithm to the problem of assigning arriving or leaving trains to the available tracks at a railway station is also discussed. 相似文献
19.
Suppose G is a graph and k,d are integers. The (k,d)-relaxed colouring game on G is a game played by two players, Alice and Bob, who take turns colouring the vertices of G with legal colours from a set X of k colours. Here a colour i is legal for an uncoloured vertex x if after colouring x with colour i, the subgraph induced by vertices of colour i has maximum degree at most d. Alice’s goal is to have all the vertices coloured, and Bob’s goal is the opposite: to have an uncoloured vertex without a legal colour. The d-relaxed game chromatic number of G, denoted by , is the least number k so that when playing the (k,d)-relaxed colouring game on G, Alice has a winning strategy. This paper proves that if G is an outerplanar graph, then for d≥6. 相似文献
20.
Jianguo Qian 《Graphs and Combinatorics》2006,22(3):391-398
A graph G is called induced matching extendable (shortly, IM-extendable) if every induced matching of G is included in a perfect matching of G. A graph G is called strongly IM-extendable if every spanning supergraph of G is IM-extendable. The k-th power of a graph G, denoted by Gk, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k.
We obtain the following two results which give positive answers to two conjectures of Yuan.
Result 1. If a connected graph G with |V(G)| even is locally connected, then G2 is strongly IM-extendable.
Result 2. If G is a 2-connected graph with |V(G)| even, then G3 is strongly IM-extendable.
Research Supported by NSFC Fund 10371102. 相似文献