Search

The classical Berge–Fulkerson conjecture states that any bridgeless cubic graph Gadmits a list of six perfect matchings such that each edge of Gbelongs to two of the perfect matchings from the list. In this short note, we discuss two statements that are consequences of this conjecture. The first of them states that for any bridgeless cubic graph G, edge eand iwith 0≤i≤2, there are three perfect matchings F1,F2,F3of Gsuch that F1∩F2∩F3=0̸and ebelongs to exactly iof these perfect matchings. The second one states that for any bridgeless cubic graph Gand its vertex v, there are three perfect matchings F1,F2,F3of Gsuch that F1∩F2∩F3=0̸and the edges incident to vbelong to k1, k2and k3of these perfect matchings, where the numbers k1, k2and k3satisfy the obvious necessary conditions. In the paper, we show that the first statement is equivalent to Fan–Raspaud conjecture. We also show that the smallest counter-example to the second one is a cyclically 4-edge-connected cubic graph.

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the numbers of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted by 𝜒=(G). It is known that the problem of computation of 𝜒=(G) is NP-hard in general and remains so for corona graphs. In this paper we consider the same model of coloring in the case of corona multiproducts of graphs. In particular, we obtain some results regarding the equitable chromatic number for the l-corona product G ◦l H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs are mostly constructive in that they lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G. Moreover, we confirm the Equitable Coloring Conjecture for corona products of such graphs. This paper extends the results from [H. Furmánczyk, K. Kaliraj, M. Kubale and V.J. Vivin, Equitable coloring of corona products of graphs, Adv. Appl. Discrete Math. 11 (2013) 103–120].

AbstractThe classical Berge–Fulkerson conjecture states that any bridgeless cubic graph admits a list of six perfect matchings such that each edge of belongs to two of the perfect matchings from the list. In this short note, we discuss two statements that are consequences of this conjecture. The first of them states that for any bridgeless cubic graph , edge and with , there are three perfect matchings of such that and belongs to exactly of these perfect matchings. The second one states that for any bridgeless cubic graph and its vertex , there are three perfect matchings of such that and the edges incident to belong to , and of these perfect matchings, where the numbers , and satisfy the obvious necessary conditions. In the paper, we show that the first statement is equivalent to Fan–Raspaud conjecture. We also show that the smallest counter-example to the second one is a cyclically 4-edge-connected cubic graph.

A graph Gis class II, if its chromatic index is at least δ + 1. Let Hbe a maximum δ‐edge‐colorable subgraph of G. The paper proves best possible lower bounds for |E(H)|/|E(G)|, and structural properties of maximum δ‐edge‐colorable subgraphs. It is shown that every set of vertex‐disjoint cycles of a class II graph with δ≥3 can be extended to a maximum δ‐edge‐colorable subgraph. Simple graphs have a maximum δ‐edge‐colorable subgraph such that the complement is a matching. Furthermore, a maximum δ‐edge‐colorable subgraph of a simple graph is always class I. © 2011 Wiley Periodicals, Inc. J Graph Theory