Strong edge-coloring of graphs with maximum degree 4 using 22 colors

In 1985, Erd?s and Ne?etril conjectured that the strong edge-coloring number of a graph is bounded above by when Δ is even and when Δ is odd. They gave a simple construction which requires this many colors. The conjecture has been verified for Δ?3. For Δ=4, the conjectured bound is 20. Previously, the best known upper bound was 23 due to Horak. In this paper we give an algorithm that uses at most 22 colors.     

On the size of critical graphs with maximum degree 8

In this paper, we prove that the average degree of an 8-critical graph is at least 13/2.     

Total choosability of planar graphs with maximum degree 4

Let G be a planar graph with maximum degree 4. It is known that G is 8-totally choosable. It has been recently proved that if G has girth g?6, then G is 5-totally choosable. In this note we improve the first result by showing that G is 7-totally choosable and complete the latter one by showing that G is 6-totally choosable if G has girth at least 5.     

On the average degree of critical graphs with maximum degree six

In this paper, we prove that the average degree of Δ-critical graphs with Δ=6 is at least . It improves the known bound for the average degree of 6-critical graphs G with |V(G)|>39.     

Decompositions for edge-coloring join graphs and cobipartite graphs

An edge-coloring is an association of colors to the edges of a graph, in such a way that no pair of adjacent edges receive the same color. A graph G is Class 1 if it is edge-colorable with a number of colors equal to its maximum degree Δ(G). To determine whether a graph G is Class 1 is NP-complete [I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981) 718-720]. First, we propose edge-decompositions of a graph G with the goal of edge-coloring G with Δ(G) colors. Second, we apply these decompositions for identifying new subsets of Class 1 join graphs and cobipartite graphs. Third, the proposed technique is applied for proving that the chromatic index of a graph is equal to the chromatic index of its semi-core, the subgraph induced by the maximum degree vertices and their neighbors. Finally, we apply these decomposition tools to a classical result [A.J.W. Hilton, Z. Cheng, The chromatic index of a graph whose core has maximum degree 2, Discrete Math. 101 (1992) 135-147] that relates the chromatic index of a graph to its core, the subgraph induced by the maximum degree vertices.     

A note on the strong edge-coloring of outerplanar graphs with maximum degree 3

A strong k-edge-coloring of a graph G is an assignment of k colors to the edges of G in such a way that any two edges meeting at a common vertex, or being adjacent to the same edge of G, are assigned different colors. The strong chromatic index of G is the smallest integer k for which G has a strong k-edge-coloring. In this paper, we have shown that the strong chromatic index is no larger than 6 for outerplanar graphs with maximum degree 3.     

Total colorings of planar graphs with large maximum degree

It is proved that a planar graph with maximum degree Δ ≥ 11 has total (vertex-edge) chromatic number $Delta; + 1. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 53–59, 1997     

Complete catalogue of graphs of maximum degree 3 and defect at most 4

We consider graphs of maximum degree 3, diameter D≥2 and at most 4 vertices less than the Moore bound M_3,D, that is, (3,D,−?)-graphs for ?≤4.We prove the non-existence of (3,D,−4)-graphs for D≥5, completing in this way the catalogue of (3,D,−?)-graphs with D≥2 and ?≤4. Our results also give an improvement to the upper bound on the largest possible number N_3,D of vertices in a graph of maximum degree 3 and diameter D, so that N_3,D≤M_3,D−6 for D≥5.     

Acyclic improper colourings of graphs with bounded maximum degree

For graphs of bounded maximum degree, we consider acyclic t-improper colourings, that is, colourings in which each bipartite subgraph consisting of the edges between two colour classes is acyclic, and each colour class induces a graph with maximum degree at most t.We consider the supremum, over all graphs of maximum degree at most d, of the acyclic t-improper chromatic number and provide t-improper analogues of results by Alon, McDiarmid and Reed [N. Alon, C.J.H. McDiarmid, B. Reed, Acyclic coloring of graphs, Random Structures Algorithms 2 (3) (1991) 277-288] and Fertin, Raspaud and Reed [G. Fertin, A. Raspaud, B. Reed, Star coloring of graphs, J. Graph Theory 47 (3) (2004) 163-182].     

The firefighter problem for graphs of maximum degree three

We show that the firefighter problem is NP-complete for trees of maximum degree three, but in P for graphs of maximum degree three if the fire breaks out at a vertex of degree at most two.     

On the maximum number of edges in quasi-planar graphs

A topological graph is quasi-planar, if it does not contain three pairwise crossing edges. Agarwal et al. [P.K. Agarwal, B. Aronov, J. Pach, R. Pollack, M. Sharir, Quasi-planar graphs have a linear number of edges, Combinatorica 17 (1) (1997) 1-9] proved that these graphs have a linear number of edges. We give a simple proof for this fact that yields the better upper bound of 8n edges for n vertices. Our best construction with 7n−O(1) edges comes very close to this bound. Moreover, we show matching upper and lower bounds for several relaxations and restrictions of this problem. In particular, we show that the maximum number of edges of a simple quasi-planar topological graph (i.e., every pair of edges have at most one point in common) is 6.5n−O(1), thereby exhibiting that non-simple quasi-planar graphs may have many more edges than simple ones.     

Acyclic vertex coloring of graphs of maximum degree 5

An acyclic vertex coloring of a graph is a proper vertex coloring such that there are no bichromatic cycles. The acyclic chromatic number of G, denoted a(G), is the minimum number of colors required for acyclic vertex coloring of graph G. For a family F of graphs, the acyclic chromatic number of F, denoted by a(F), is defined as the maximum a(G) over all the graphs G∈F. In this paper we show that a(F)=8 where F is the family of graphs of maximum degree 5 and give a linear time algorithm to achieve this bound.     

Representing edge intersection graphs of paths on degree 4 trees

Let P be a collection of nontrivial simple paths on a host tree T. The edge intersection graph of P, denoted by EPT(P), has vertex set that corresponds to the members of P, and two vertices are joined by an edge if and only if the corresponding members of P share at least one common edge in T. An undirected graph G is called an edge intersection graph of paths in a tree if G=EPT(P) for some P and T. The EPT graphs are useful in network applications. Scheduling undirected calls in a tree network or assigning wavelengths to virtual connections in an optical tree network are equivalent to coloring its EPT graph.An undirected graph G is chordal if every cycle in G of length greater than 3 possesses a chord. Chordal graphs correspond to vertex intersection graphs of subtrees on a tree. An undirected graph G is weakly chordal if every cycle of length greater than 4 in G and in its complement possesses a chord. It is known that the EPT graphs restricted to host trees of vertex degree 3 are precisely the chordal EPT graphs. We prove a new analogous result that weakly chordal EPT graphs are precisely the EPT graphs with host tree restricted to degree 4. Moreover, this provides an algorithm to reduce a given EPT representation of a weakly chordal EPT graph to an EPT representation on a degree 4 tree. Finally, we raise a number of intriguing open questions regarding related families of graphs.     

Acyclic improper colouring of graphs with maximum degree 4

A k-colouring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclic k-colourings such that each colour class induces a graph with a given(hereditary) property. In particular, we consider acyclic k-colourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyclic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with Δ(G) 4 can be acyclically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.     

Distance graphs with maximum chromatic number

The distance graph G(D) has the set of integers as vertices and two vertices are adjacent in G(D) if their difference is contained in the set D⊂Z. A conjecture of Zhu states that if the chromatic number of G(D) achieves its maximum value |D|+1 then the graph has a triangle. The conjecture is proven to be true if |D|?3. We prove that the chromatic number of a distance graph with D={a,b,c,d} is five only if either D={1,2,3,4k} or D={a,b,a+b,b-a}. This confirms a stronger version of Zhu's conjecture for |D|=4, namely, if the chromatic number achieves its maximum value then the graph contains K₄.     

4-chromatic edge critical Grötzsch-Sachs graphs

Let G be a 4-regular plane graph and suppose that G has a cycle decomposition S (i.e., each edge of G is in exactly one cycle of the decomposition) with every pair of adjacent edges on a face always in different cycles of S. Such a graph G arises as a superposition of simple closed curves in the plane with tangencies disallowed. Two 4-chromatic edge critical graphs of order 48 generated by four curves are presented.     

On second order degree of graphs

Given a vertex v of a graph G the second order degree of v denoted as d 2(v) is defined as the number of vertices at distance 2 from v.In this paper we address the following question:What are the sufficient conditions for a graph to have a vertex v such that d2(v) ≥ d(v),where d(v) denotes the degree of v? Among other results,every graph of minimum degree exactly 2,except four graphs,is shown to have a vertex of second order degree as large as its own degree.Moreover,every K-4-free graph or every maximal planar graph is shown to have a vertex v such that d2(v) ≥ d(v).Other sufficient conditions on graphs for guaranteeing this property are also proved.     

Bipartite graphs with the maximum sum of squares of degrees

In this paper we determine all the bipartite graphs with the maximum sum of squares of degrees among the ones with a given number of vertices and edges.